Parallel-Machine Batching and Scheduling to Minimize Total Completion Time

Abstract

We consider a scheduling problem in which n independent and simultaneously available jobs are to be processed on m identical parallel machines. The jobs have to be batched as well as scheduled. The completion time of a job is defined as the completion time of the batch containing it. A constant set-up time is incurred whenever a batch is formed. The problem is to batch and schedule jobs so that the total completion time of the jobs is minimized. We first present some properties and then develop a dynamic programming algorithm to solve this problem. The running time of our algorithm is O(mn^m+1). When job processing times are identical, we show that the problem reduces to the corresponding single-machine problem, which has been well solved in the literature.

Additional information

Notes on contributors

T.C.E. Cheng

T.C.E. Cheng is Vice President (Research and Postgraduate Studies) and Professor of Management in The Hong Kong Polytechnic University. He obtained a Ph.D. in Operations Research from the University of Cambridge in 1984. His research interests are in operations research and operations management. Recipient of the Outstanding Young Engineer of the Year Award of the IIE in 1992, Professor Cheng has published extensively in a variety of academic and professional journals and two books.

Z.-L. Chen

Z.-L. Chen is a doctoral student in the Department of Civil Engineering and Operations Research, Princeton University. He has published a number of papers in various mathematical and operations research journals. His research interests are in combinatorial optimization and stochastic programming.

M.Y. Kovalyov

M.Y. Kovalyov is Senior Researcher at the Institute of Engineering Cybernetics, Belarus Academy of Sciences, Minsk, Belarus. He received the Candidate of Sciences degree in Mathematical Cybernetics from the Institute of Mathematics, Minsk, in 1986. He was a UNESCO Fellow at Erasmus University Rotterdam in 1989 and a Visiting Scholar at The Hong Kong Polytechnic University in 1994 and 1995. His research interests are in scheduling and discrete optimization.

B.M.T. Lin

B.M.T. Lin is Associate Professor in the Department of Information Management, Ming-Chuan College, Chinese Taiwan. He received a B.S. and an M.S. in Information Science and a Ph.D. in Computer Science and Information Engineering from the National Chiao-Tung University, Chinese Taiwan. He has published in many operational research and mathematical journals. His main areas of interest include scheduling theory and decision support systems.