Article ID: | iaor20041008 |
Country: | United Kingdom |
Volume: | 54 |
Issue: | 5 |
Start Page Number: | 499 |
End Page Number: | 506 |
Publication Date: | May 2003 |
Journal: | Journal of the Operational Research Society |
Authors: | Cheng T.C.E., Kovalyov M.Y., Ng C.T. Daniel |
Keywords: | production |
We study a problem of scheduling n jobs on a single machine in batches. A batch is a set of jobs processed contiguously and completed together when the processing of all jobs in the batch is finished. Processing of a batch requires a machine setup time dependent on the position of this batch in the batch sequence. Setup times and job processing times are continuously controllable, that is, they are real-valued variables within their lower and upper bounds. A deviaton of a setup time or job processing time from its upper bound is called a compression. The problem is to find a job sequence, its partition into batches, and the values for setup times and job processing times such that (a) total job completion time is minimized, subject to an upper bound on total weighted setup time and job processing time compression, or (b) a linear combination of total job completion time, total setup time compression, and total job processing time compression is minimized. Properties of optimal solutions are established. If the lower and upper bounds on job processing times can be similarly ordered or the job sequence is fixed, then