Browsing by Author "Lin, Bertrand M. T."

Now showing 1 - 20 of 32

A Decision Model for Human Resource Allocation in Project Management of Software Development
(2020-01-01)
Chiang, Hui Yi
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
In project management, especially of software development, human resource allocation is critical not only for project success including timely delivery and products quality but also for cost estimation to a software company to decide to contract projects or not. Many approaches have been proposed to provide assistance for human resource allocation in view of minimizing project duration and project cost or maximizing revenue and efficiency. These approaches may sometimes not be comprehensive in real-world environments without addressing some key factors like transferring cost, communication, and negative efficiency, which usually have crucial impacts on assignment applicability. This article is proposing a framework for assisting a software company to evaluate existing resource for making decisions on whether the estimation of the tender is feasible, and assisting to make human resource allocation for team formation in fixed project duration with labor skill and budget constraint. Within consideration of both the cost and the efficiency, the performance is maximized to verges on the customers& x2019; expectations in software development project management on the basis of a real case. Before forming a team for a specific project with well-defined periods and numbers of people with different project roles, the values of key factors in the framework are calculated with individual foundation of computation. We formulate the decision process in integer programming models, and a simulation study is conducted to demonstrate the applicability of the proposed model to assist the decision making process of software companies for team formation. The results of four variants for maximum skill efficiency or minimum hiring cost are illustrated with different considerations of both key factors are included or not proposed in this paper, and demonstrate that these factors could bring out different sources to help companies in making further evaluations for allocating staff in a software development project.
A NOTE ON NETWORK REPAIR CREW SCHEDULING AND ROUTING FOR EMERGENCY RELIEF DISTRIBUTION PROBLEM
(2019-10-01)
Hong, Huai-Che
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper proposes a dynamic programming algorithm for the NRCSRP with multiple crews. This algorithm also improves the existing algorithm for the problem with a single crew.
A two-machine flowshop problem with processing time-dependent buffer constraints-An application in multimedia presentations
(2009-04-01)
Lin, Feng-Cheng
;
Hong, Jen-Shin
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
To have a quality multimedia presentation through networks, its presentation lag needs to be controlled. One way to reduce the lag is to prefetch the media objects before their due dates. This paper explores techniques for optimizing the object sequence in a prefetch-enabled TV-like presentation. An optimal solution is the one with which the presentation lag is minimized. We formulate the problem into a two-machine flowshop scheduling problem with a single chain precedence constraint and a player-side buffer constraint. The player-side buffer is "processing time-dependent" and distinguished from the conventional item-based intermediate buffer constraints discussed in previous flowshop studies. We prove the problem to he strongly NP-hard. A branch and bound algorithm equipped with four lower bounds and an NEH-based upper bound is developed. The simulation results show that the average gaps between the overall lower bounds and the NEH-based upper bound are less than 3% for problems with a large buffer size, and less than 13% for problems with a small buffer size and high density of precedence constraints. For applications where the media objects are delivered through extremely busy servers with which only very restricted CPU resources can be allocated for computation, the CDS-based algorithm provides better sequences than the NEH-based algorithm. (C) 2008 Elsevier Ltd. All rights reserved.
Acquisition planning and scheduling of computing resources
(2016-12)
Yang, Chien-Nan
;
Lin, Bertrand M. T.
;
Hwang, F. J.
;
Wang, Meng-Chun
;
資訊管理與財務金融系註：原資管所+財金所
Cloud computing has been attracting considerable attention since the last decade. This study considers a decision problem formulated from the use of computing services over the Internet. An agent receives orders of computing tasks from his/her clients and on the other hand he/she acquires computing resources from computing service providers to fulfill the requirements of the clients. The processors are bundled as packages according to their speeds and the business strategies of the providers. The packages are rated at a certain pricing scheme to provide flexible purchasing options to the agent. The decision of the agent is to select the packages which can be acquired from the service providers and then schedule the tasks of the clients onto the processors of the acquired packages such that the total cost, including acquisition cost and scheduling cost (total weighted tardiness), is minimized. In this study, we present an integer programming model to formulate the problem and propose several solution methods to produce acquisition and scheduling plans. Ten well-known heuristics of parallel-machine scheduling are adapted to fit into the studied problem so as to provide initial solutions. Tabu search and genetic algorithm are tailored to reflect the problem nature for improving upon the initial solutions. We conduct a series of computational experiments to evaluate the effectiveness and efficiency of all the proposed algorithms. The results of the numerical experiments reveal that the proposed tabu search and genetic algorithm can attain significant improvements. (C) 2016 Elsevier Ltd. All rights reserved.
Ant colony optimization for dynamic routing and wavelength assignment in WDM networks with sparse wavelength conversion
(2011-03-01)
Chen, Ming-Tsung
;
Lin, Bertrand M. T.
;
Tseng, Shian-Shyong
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
Since optical WDM networks are becoming one of the alternatives for building up backbones, dynamic routing, and wavelength assignment with delay constraints (DRWA-DC) in WDM networks with sparse wavelength conversions is important for a communication model to route requests subject to delay bounds. Since the NP-hard minimum Steiner tree problem can be reduced to the DRWA-DC problem, it is very unlikely to derive optimal solutions in a reasonable time for the DRWA-DC problem. In this paper, we circumvent to apply a meta-heuristic based upon the ant colony optimization (ACO) approach to produce approximate solutions in a timely manner. In the literature, the ACO approach has been successfully applied to several well-known combinatorial optimization problems whose solutions might be in the form of paths on the associated graphs. The ACO algorithm proposed in this paper incorporates several new features so as to select wavelength links for which the communication cost and the transmission delay of routing the request can be minimized as much as possible subject to the specified delay bound. Computational experiments are designed and conducted to study the performance of the proposed algorithm. Comparing with the optimal solutions found by an ILP formulation, numerical results evince that the ACO algorithm is effective and robust in providing quality approximate solutions to the DRWA-DC problem. (C) 2010 Elsevier Ltd. All rights reserved.
Batch scheduling in differentiation flow shops for makespan minimisation
(2013-09-01)
Huang, Ting-Chih
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper considers a two-stage three-machine differentiation flow shop that comprises a common machine at stage 1 and two independent dedicated machines at stage 2. Two types of jobs are to be processed. All jobs must visit the stage-1 machine, and then the jobs of each type proceed to their dedicated machine for stage-2 processing. The stage-1 machine processes the jobs in batches, each of which, whenever formed, requires a constant setup time. The objective is to find a schedule that attains the minimum makespan. While the problem is strongly NP-hard, we investigate the case where the processing sequences of the two types of jobs are given and fixed. A polynomial-time dynamic programming algorithm is designed to solve this problem. We then deploy this algorithm to compute the lower bounds of the general problem.
Clarification of lower bounds of two-machine flow-shop scheduling to minimize total late work
(2019-07-03)
Blazewicz, Jacek
;
Chen, Xin
;
Lee, Richard C. T.
;
Lin, Bertrand M. T.
;
Lin, Feng-Cheng
Complexity of server scheduling on parallel dedicated machines subject to fixed job sequences
(1970-01-01)
Cheng, T. C. E.
;
Kravchenko, Svetlana A.
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
We study server scheduling on parallel dedicated machines to minimize the makespan subject to given processing sequences. Before a job starts its processing on its designated machine, a loading operation must be performed, which is undertaken by a server shared by all the jobs. While the two-machine problem is polynomially solvable, we show that the problem becomes binaryNP-hard when the number of machines is three, and propose a pseudo-polynomial algorithm to solve the problem with a constant number of machines.
Coupled-task scheduling on a single machine subject to a fixed-job-sequence
(2011-05-01)
Hwang, F. J.
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper investigates single-machine coupled-task scheduling where each job has two tasks separated by an exact delay. The objective of this study is to schedule the tasks to minimize the makespan subject to a given job sequence. We introduce several intriguing properties of the fixed-job-sequence problem under study. While the complexity status of the studied problem remains open, an O(n(2)) algorithm is proposed to construct a feasible schedule attaining the minimum makespan for a given permutation of 2n tasks abiding by the fixed-job-sequence constraint. We investigate several polynomially solvable cases of the fixed-job-sequence problem and present a complexity graph of the problem. (C) 2011 Elsevier Ltd. All rights reserved.
Discrete particle swarm optimization for materials acquisition in multi-unit libraries
(2012)
Wu, Yi-Ling
;
Shyu, Shyong Jian
;
Ho, Tsu-Feng
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
With limited budget and inflation rate, the materials acquisition in multi-unit libraries has been a challenging issue all over the world. The materials acquisition for multi-unit libraries can be regarded as a generalized version of the knapsack problem, which was known to be NP-hard, with much more constraints. Thus, it can be computationally expensive to solve the problem. In this paper, the materials acquisition problem in multi-unit libraries is formulated as an integer programming model, and two different constraint-handling mechanisms applied in discrete particle swarm optimization algorithm for obtaining the near optimal solution are presented. It is evident from our computational results that one constraint-handling mechanism can solve the problem effectively and efficiently, while the other one takes more time.
Discrete Particle Swarm Optimization with Scout Particles for Library Materials Acquisition
(2013)
Wu, Yi-Ling
;
Ho, Tsu-Feng
;
Shyu, Shyong Jian
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
Materials acquisition is one of the critical challenges faced by academic libraries. This paper presents an integer programming model of the studied problem by considering how to select materials in order to maximize the average preference and the budget execution rate under some practical restrictions including departmental budget, limitation of the number of materials in each category and each language. To tackle the constrained problem, we propose a discrete particle swarm optimization (DPSO) with scout particles, where each particle, represented as a binary matrix, corresponds to a candidate solution to the problem. An initialization algorithm and a penalty function are designed to cope with the constraints, and the scout particles are employed to enhance the exploration within the solution space. To demonstrate the effectiveness and efficiency of the proposed DPSO, a series of computational experiments are designed and conducted. The results are statistically analyzed, and it is evinced that the proposed DPSO is an effective approach for the studied problem.
Fast approximation algorithms for bi-criteria scheduling with machine assignment costs
(2014-10-01)
Lee, Kangbok
;
Leung, Joseph Y-T.
;
Jia, Zhao-hong
;
Li, Wenhua
;
Pinedo, Michael L.
We consider parallel machine scheduling problems where the processing of the jobs on the machines involves two types of objectives. The first type is one of two classical objective functions in scheduling theory: either the total completion time or the makespan. The second type involves an actual cost associated with the processing of a specific job on a given machine: each job-machine combination may have a different cost. Two bi-criteria scheduling problems are considered: (1) minimize the maximum machine cost subject to the total completion time being at its minimum, and (2) minimize the total machine cost subject to the makespan being at its minimum. Since both problems are strongly NP-hard, we propose fast heuristics and establish their worst-case performance bounds. (C) 2014 Elsevier B.V. All rights reserved.
Flow shop non-idle scheduling and resource-constrained scheduling
(2016-03)
Tsai, Yen-Shing
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
In a two-machine flow shop, the problem seeks to select and schedule jobs such that the processing of the selected jobs does not contain any idle time. The objective is to maximize the number of selected jobs. The problem is studied in the context of a resource-constrained scheduling problem. An O(n(2)) dynamic programming algorithm is proposed. The problem becomes ordinary NP-hard when job weights are introduced. A heuristic is designed and its performance ratio is analysed to be 3.
Minimizing the total weighted completion time in the relocation problem
(2010-04-01)
Kononov, Alexander V.
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper studies the minimization of total weighted completion time in the relocation problem on a single machine. The relocation problem, formulated from an area redevelopment project, can be treated as a resource-constrained scheduling problem. In this paper, we show four special cases to be NP-hard in the strong sense. Problem equivalence between the unit-weighted case and the UET (unit-execution-time) case is established. For two further restricted special cases, we present a polynomial time approximation algorithm and show its performance ratio to be 2.
Parallel dedicated machine scheduling with conflict graphs
(2018-10-01)
Hong, Huai-Che
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper investigates a variant of parallel-machine scheduling problems with conflict constraints. A set of identical parallel machines is available for processing a set of jobs subject to conflict constraints, which specify pairs of jobs that are mutually disjoint due to resource availability. Jobs conflicting to each other cannot be processed simultaneously. The scheduling problem is to construct a feasible schedule that optimizes the considered managerial performance measures. This paper discusses the specific two-machine setting where each machine has a designated set of jobs to process. We give NP-hardness proofs for the case with the presence of a fixed processing sequence on one of the machines. Polynomial-time dynamic programming algorithms are proposed to produce optimal schedules for the case where the processing sequences on both machines are known and fixed a priori.
Parallel-machine scheduling to minimize tardiness penalty and power cost
(2013-01-01)
Fang, Kuei-Tang
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
Traditional research on machine scheduling focuses on job allocation and sequencing to optimize certain objective functions that are defined in terms of job completion times. With regard to environmental concerns, energy consumption becomes another critical issue in high-performance systems. This paper addresses a scheduling problem in a multiple-machine system where the computing speeds of the machines are allowed to be adjusted during the course of execution. The CPU adjustment capability enables the flexibility for minimizing electricity cost from the energy saving aspect by sacrificing job completion times. The decision of the studied problem is to dispatch the jobs to the machines as well as to determine the job sequence and processing speed of each machine with the objective function comprising of the total weighted job tardiness and the power cost. We give a formal formulation, propose two heuristic algorithms, and develop a particle swarm optimization (PSO) algorithm to effectively tackle the problem. Since the existing solution representations do not befittingly encode the decisions involved in the studied problem into the PSO algorithm, we design a tailored encoding scheme which can embed all decisional information in a particle. A computational study is conducted to investigate the performances of the proposed heuristics and the PSO algorithm. (C) 2012 Elsevier Ltd. All rights reserved.
Preemptive parallel-machine scheduling problem of maximizing the number of on-time jobs
(2019-08-01)
Hung, Hui-Chih
;
Lin, Bertrand M. T.
;
Posner, Marc E.
;
Wei, Jun-Min
;
工業工程與管理學系
This paper investigates the classical preemptive parallel-machine scheduling problem of maximizing number of on-time jobs. While the problem is known to be NP-hard, no theoretical analysis of approximation algorithms exists in the literature. As part of the analysis, a new non-standard mixed integer formulation is developed. We propose heuristics based on different design strategies. These heuristics have asymptotically tight relative errors of 1/2. Experimental tests evaluate the computational performance of the procedures.
Preemptive Parallel-Machine Scheduling with a Common Server to Minimize Makespan
(2017-08-01)
Cheng, T. C. E.
;
Kravchenko, Svetlana A.
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
We consider parallel-machine scheduling with a common server and job preemption to minimize the makespan. While the non-preemptive version of the problem is strongly NP-hard, the complexity status of the preemptive version has remained open. We show that the preemptive version is NP-hard even if there is a fixed number of machines. We give a pseudo-polynomial time algorithm to solve the case with two machines. We show that the case with an arbitrary number of machines is unary NP-hard, analyze the performance ratios of some natural heuristic algorithms, and present several solvable special cases. (C) 2017 Wiley Periodicals, Inc.
Relocation scheduling subject to fixed processing sequences
(2016-04)
Lin, Bertrand M. T.
;
Hwang, F. J.
;
Kononov, Alexander V.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This study addresses a relocation scheduling problem that corresponds to resource-constrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in time, where and are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NP-hard in the ordinary sense, and the case with a common job processing length is solvable in time. The studied problem for the minimization of number of tardy jobs is solvable in time. The solvability of the common-processing-time problems can be generalized to the m-machine cases, where .
Resource-constrained scheduling with optional recycling operations
(2015-12-01)
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper introduces a scheduling problem with a variant of resource constraint that stems from a relocation project. We also propose the concept of optional recycling operations, in which recycling operations are separated from the processing of jobs and recycling operations are exercised only when necessary. An integer program is proposed to formulate the problem and facilitate complexity classification. We propose a pseudo-polynomial time dynamic program, and then classify the complexity status of several restricted cases. (C) 2015 Elsevier Ltd. All rights reserved.