Browsing by Author "Cheng, T. C. E."

Now showing 1 - 12 of 12

A scheduling model for the refurbishing process in recycling management
(2013-11-01)
Cheng, T. C. E.
;
Lin, B. M. T.
;
Tian, Y.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
We propose from the perspective of operations scheduling a novel model of the refurbishing process in recycling management. We model the refurbishing process as a two-stage flowshop that dismantles products into parts in stage one and refurbishes the parts on dedicated machines in stage two. The model also features that the performance measure of a schedule is defined by operation-based completion times, which is different from the job-based performance measures traditionally adopted in the scheduling literature. We analyse the optimality properties and computational complexity of some special cases of the problem. We derive lower bounds on the optimal solution based on a disaggregation technique and the assignment problem, and develop dominance rules incorporating estimates of the effects of partial schedules on unscheduled jobs. We present a heuristic approach, based on LP relaxation, and analyse its performance ratio. We also develop two metaheuristic algorithms, based on iterated local search and ant colony optimisation, to produce approximate solutions. The results of computational experiments show that the metaheuristics generate better solutions than the simple weighted shortest processing time dispatching rule, and the NEH-based and CDS-based algorithms, which are commonly deployed to treat the classical two-machine flowshop scheduling problem.
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.
Demonstrating Johnson's algorithm via resource-constrained scheduling
(2017-01-01)
Cheng, T. C. E.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
The celebrated Johnson's algorithm to solve the two-machine flowshop scheduling problem to minimise the makespan plays a prominent role in scheduling research. In using resource-constrained scheduling to interpret Johnson's algorithm in teaching scheduling theory and operations management, we have received positive student feedback on the perceived intuition. We demonstrate this idea and show that the resource-constrained scheduling concept also helps simplify the proofs of some classical scheduling results.
Johnson's rule, composite jobs and the relocation problem
(2009-02-01)
Cheng, T. C. E.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
Two-machine flowshop scheduling to minimize makespan is one of the most well-known classical scheduling problems. Johnson's rule for solving this problem has been widely cited in the literature. We introduce in this paper the concept of composite job, which is an artificially constructed job with processing times such that it will incur the same amount of idle time oil the second machine as that incurred by a chain of jobs in a given processing sequence. This concept due to Kurisu first appeared in 1976 to deal with the two-machine flowshop scheduling problem involving precedence constraints among the jobs. We show that this concept can be applied to reduce the computational time to solve some related scheduling problems. We also establish a link between solving the two-machine flowshop makespan minimization problem using Johnson's rule and the relocation problem introduced by Kaplan. We present an intuitive interpretation of Johnson's rule in the context of the relocation problem. (c) 2007 Elsevier B.V. All rights reserved.
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.
Resource-constrained flowshop scheduling with separate resource recycling operations
(2012-06-01)
Cheng, T. C. E.
;
Lin, B. M. T.
;
Huang, H. L.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper considers the relocation problem arising from public re-development projects cast as a two-machine flowshop scheduling problem. In such a project, some buildings need to be torn down and re-constructed. The two processes of tearing down and re-constructing each building are often viewed as a single operation. However, under certain circumstances, the re-construction process, i.e., the resource recycling process, can be viewed as a separate operation. In this paper we regard these two processes as separate on the assumption that they are handled by different working crews. We formulate the problem as a resource-constrained two-machine flowshop scheduling problem with the objective of finding a feasible re-development sequence that minimizes the makespan. We provide problem formulations, discuss the complexity results, and present polynomial algorithms for various special cases of the problem. (C) 2010 Elsevier Ltd. All rights reserved.
Scheduling in an assembly-type production chain with batch transfer
(2007-04-01)
Lin, B. M. T.
;
Cheng, T. C. E.
;
Chou, A. S. C.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper addresses a three-machine assembly-type flowshop scheduling problem, which frequently arises from manufacturing process management as well as from supply chain management. Machines one and two are arranged in parallel for producing component parts individually, and machine three is an assembly line arranged as the second stage of a flowshop for processing the component parts in batches. Whenever a batch is formed on the second-stage machine, a constant setup time is required. The objective is to minimize the makespan. In this study we establish the strong NP-hardness of the problem for the case where all the jobs have the same processing time on the second-stage machine. We then explore a useful property, based upon which a special case can be optimally solved in polynomial time. We also study several heuristic algorithms to generate quality approximate solutions for the general problem. Computational experiments are conducted to evaluate the effectiveness of the algorithms. (c) 2005 Elsevier Ltd. All rights reserved.
Scheduling of a two-stage differentiation flowshop to minimize weighted sum of machine completion times
(2009-11-01)
Cheng, T. C. E.
;
Lin, B. M. T.
;
Tian, Y.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper considers the problem of scheduling a two-stage flowshop that consists of a common critical machine in stage one and two independent dedicated machines in stage two. All the jobs require processing first on the common critical machine. Each job after completing its critical operation in stage one will proceed to the dedicated machine of its type for further processing in stage two. The objective is to minimize the weighted sum of stage-two machine completion times. We show that the problem is strongly NP-hard, and develop an O(n(3)) polynomial time algorithm to solve the special case where the sequences of both types of jobs are given. We also design an approximation algorithm with a tight performance ratio of 4/3 for the general case. (C) 2009 Elsevier Ltd. All rights reserved.
Scheduling step-deteriorating jobs to minimize the total completion time
(2020-06-01)
Cheng, T. C. E.
;
Kravchenko, Svetlana A.
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
We consider single-machine scheduling to minimize the total completion time, where the processing time of a job is a step function of its start time. In this paper we establish the complexity status of the problem by proving its NP-hardness and developing a dynamic programming algorithm that solves the problem in pseudo-polynomial time.
Scheduling with Centralized and Decentralized Batching Policies in Concurrent Open Shops
(2011-02-01)
Lin, B. M. T.
;
Cheng, T. C. E.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This article considers batch scheduling with centralized and decentralized decisions. The context of our study is concurrent open shop scheduling where the jobs are to be processed on a set of independent dedicated machines, which process designated operations of the jobs in batches. The hatching policy across the machines can be centralized or decentralized. We study such scheduling problems with the objectives of minimizing the maximum lateness, weighted number of tardy jobs, and total weighted completion time, when the job sequence is determined in advance. We present polynomial time dynamic programming algorithms for some cases of these problems and pseudo-polynomial time algorithms for some problems that are NP-hard in the ordinary sense. (C) 2010 Wiley Periodicals, Inc. Naval Research Logistics 58: 17-27, 2011
Server scheduling on parallel dedicated machines with fixed job sequences
(2019-06-01)
Cheng, T. C. E.
;
Kravchenko, Svetlana A.
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
We consider server scheduling on parallel dedicated machines to minimize the makespan. Each job has a loading operation and a processing operation. The loading operation requires a server that serves all the jobs. Each machine has a given set of jobs to process, and the processing sequence is known and fixed. We design a polynomial-time algorithm to solve the two-machine case of the problem. When the number of machines is arbitrary, the problem becomes strongly NP-hard even if all the jobs have the same processing length or all the loading operations require a unit time. We design two heuristic algorithms to treat the case where all the loading times are unit and analyze their performance.
Two-agent singe-machine scheduling with release times to minimize the total weighted completion time
(2013-01-01)
Cheng, T. C. E.
;
Chung, Yu-Hsiang
;
Liao, Shan-Ci
;
Lee, Wen-Chiung
;
應用化學系
In many management situations multiple agents pursuing different objectives compete on the usage of common processing resources. In this paper we study a two-agent single-machine scheduling problem with release times where the objective is to minimize the total weighted completion time of the jobs of one agent with the constraint that the maximum lateness of the jobs of the other agent does not exceed a given limit. We propose a branch-and-bound algorithm to solve the problem, and a primary and a secondary simulated annealing algorithm to find near-optimal solutions. We conduct computational experiments to test the effectiveness of the algorithms. The computational results show that the branch-and-bound algorithm can solve most of the problem instances with up to 24 jobs in a reasonable amount of time and the primary simulated annealing algorithm performs well with an average percentage error of less than 0.5% for all the tested cases. (C) 2012 Elsevier Ltd. All rights reserved.