Batch scheduling with controllable setup and processing times to minimize total completion time
- PDF / 222,104 Bytes
- 8 Pages / 595 x 794 pts Page_size
- 26 Downloads / 206 Views
r 2003 Operational Research Society Ltd. All rights reserved. 0160-5682/03 $25.00 www.palgrave-journals.com/jors
Batch scheduling with controllable setup and processing times to minimize total completion time CT Daniel Ng1*, TCE Cheng1 and MY Kovalyov2 1
The Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong; and 2Belarus State University, Minsk, Belarus 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 deviation 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 Oðn3 log nÞ and Oðn5 Þ time algorithms are developed to solve cases (a) and (b), respectively. If all job processing times are fixed or all setup times are fixed, then more efficient algorithms can be devised to solve the problems. Journal of the Operational Research Society (2003) 54, 499–506. doi:10.1057/palgrave.jors.2601537 Keywords: scheduling; single machine; batching; minimizing total completion time; controllable setup and processing times
Problem formulation and literature review The problem of batching and scheduling n independent and nonpre-emptive jobs available for processing at time zero on a single machine is studied. Jobs assigned to the same batch are processed contiguously and are completed together when the processing of the last job in the batch is finished. The batch processing time is equal to the sum of the processing times of its jobs. A machine setup time precedes the processing of each batch. The processing time of job j is a variable pj 2 ½lj ; uj , 0plj puj , j ¼ 1; . . . ; n, and the setup time of a batch sequenced rth is a variable sr 2 ½ar ; br , 0par pbr , r ¼ 1; . . . ; k, where k is the number of batches in the schedule. The upper bounds uj and br can be viewed as normal processing and setup times, respectively, that can be compressed through allocation of additional amounts of resources to them. There are costs a and b associated with each unit of job processing time compression and setup time compression, respectively. Denote xj ¼ uj pj and yr ¼ br sr . Given pj , j ¼ 1; . . . ; n, and sr , r ¼ 1; . . . ;
Data Loading...
