We study the problem of scheduling jobs on a single batch processing machine to minimize the total weighted completion time. A batch processing machine is one that can process a number of jobs simultaneously as a batch. The processing time of a batch is given by the processing time of the longest job in the batch. We present a branch and bound algorithm to obtain optimal solutions and develop lower bounds and dominance conditions. We also develop a number of heuristics and evaluate their performance through extensive computational experiments. Results show that two of the heuristics consistently generate high‐quality solutions in modest CPU times.
AhmadiJ. H.AhmadiR. H.DasuS., and TangC. S. (1992), “Batching and Scheduling Jobs on Batch and Discrete Processors,”Operations Research, 40, 750–763.
2.
ChandruV.LeeC. Y. and UzsoyR. (1993a), “Minimizing Total Completion Time on Batch Processing Machines,”International Journal of Production Research, 31, 2097–2121.
3.
ChandruV. (1993b), “Minimizing Total Completion Time on a Batch Processing Machine with Job Families,”Operations Research Letters, 13, 61–65.
4.
DobsonG., and NambinadomR. S. (1992), The Batch Loading and Scheduling Problem, Research Report, Simon School of Business Administration, University of Rochester, Rochester, NY.
5.
EastmanW. L.EvenS., and IsaacsI. M. (1964), “Bounds for the Optimal Scheduling of n Jobs on m Processors,”Management Science, 11, 268–279.
6.
FrenchS. (1982), Sequencing and Scheduling: An Introduction to. the Mathematics of the Job‐Shop.John Wiley, New York.
7.
GareyM. R., and JohnsonD. S. (1979) Computers and Intractability: A Guide to the Theory of NP‐Completeness. W. H. Freeman, New York.
8.
GlasseyC. R., and WengW. (1991), “Dynamic Batching Heuristics for Simultaneous Processing,”IEEE Transactions on Semiconductor Manufacturing, 4, 77–82.
9.
HochbaumD. S., and LandyD. (1994), Algorithms and Heuristics for Scheduling Semiconductor Burn‐in Operations, Research Report, Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA.
10.
IkuraY., and GimpleM. (1986), “Scheduling Algorithms for a Single Batch Processing Machine,”Operations Research Letters, 5, 61–65.
11.
LawlerE. L.LenstraJ. K.Rinnooy KanH. G., and ShmoysD. B. (1993), “Sequencing and Scheduling: Algorithms and Complexity” in Handbooks in Operations Research and Management Science Vol. 4: Logistics of Production and Inventory, GravesS. C.Rinnooy KanA. H. G.ZipkinP. H. (eds.), North Holland, Amsterdam, 445–522.
12.
LeeC. Y.UzsoyR., and Martin‐VegaL. A. (1992), “Efficient Algorithms for Scheduling Semiconductor Burn‐in Operation,”Operations Research, 40, 764–775.
13.
LenstraJ. K.Rinnooy KanA. H. G., and BruckerP. (1977), “Complexity of Machine Scheduling Problems,”Annals of Discrete Mathematics, 1, 343–362.
14.
OvacikI. M., and UzsoyR. (1992), “A Shifting Bottleneck Algorithm for Scheduling Semiconductor Testing Operations,”Journal of Electronics Manufacturing, 2, 119–134.
15.
UzsoyR. (1994), “Scheduling Batch Processing Machines with Nonidentical Job Sizes,”International Journal of Production Research, 32, 1615–1635.
16.
UzsoyR.LeeC. Y., and Martin‐VegaLouis A. (1992), “A Review of Production Planning and Scheduling Models in Semiconductor Industry‐Part I: System Characteristics, Performance Evaluation and Production Planning,”IIE Transactions on Scheduling & Logistics, 24, 47–61.
17.
UzsoyR. (1994), “A Review of Production Planning and Scheduling Models in Semiconductor Industry‐Part II: Shop‐Floor Control,”IIE Transaction on Scheduling & Logistics, 26, 44–55.
18.
WengW., and LeachmanR. C. (1990), Furnace Scheduling, Research Report, Department of Industrial Engineering and Operations Research, University of California, Berkeley, CA.
