Article Contents
Article Contents

# Single machine batch scheduling problem to minimize makespan with controllable setup and jobs processing times

• This paper concerns with a single-machine scheduling problem under batch availability in which both the setup of each batch and the processing times of jobs are controllable by allocating a resource. The completion time of a job in a batch is that of the last job in the batch. Two batch scheduling problems are investigated. The objective is to determine the job sequence, the partition of the job sequence into batches and the resource allocation scheme to minimize makespan, subject to the total amount of resource is bounded by a given value $U$ in the first problem; while in the second problem is to minimize a total cost of makespan and resource without resource limitation, respectively. We show that the problems underlying can be solved in polynomial time and present optimal algorithms.
Mathematics Subject Classification: Primary: 90B35; Secondary: 47N10.

 Citation:

•  [1] T. C. E. Cheng, A. Janiak and M. Y. Kovalyov, Single machine batch scheduling with resource dependent setup processing times, European Journal of Operational Research, 135 (2001), 177-183. [2] R. L. Graham, E. L. Lawler, J. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 3 (1979), 287-326. [3] C. N. Potts, Van Wassenhove and L. Y. Gao, Integrated scheduling with batching and a lot-sizing: a review of algorithms and complexity, Journal of Operational Research Society, 43 (1991), 395-406. [4] C. N. Potts and M. Y. Kovalyov, Scheduling with batching: a review, European Journal of Operational Research, 120 (2000), 228-249.doi: 10.1016/S0377-2217(99)00153-8. [5] A. Rudek and R. Rudek, A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models, Computer and Mathematics with Applications, 4 (2011), 1870-1878. [6] D. Shabtay and G. Steiner, A survey of scheduling with controllable processing times, Discrete Applied Mathematics, 13 (2007), 1643-1666.doi: 10.1016/j.dam.2007.02.003. [7] R. G. Vickson, Two single-machine sequencing problems involing controllable job processing times, AIIE Transactions, 3 (1980), 258-262.doi: 10.1080/05695558008974515.