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

Chengxin  Luo

doi:10.3934/naco.2015.5.71

Article Contents

2015, Volume 5, Issue 1: 71-77. Doi: 10.3934/naco.2015.5.71

This issue Previous Article Optimal dilution strategy for a microbial continuous culture based on the biological robustness Next Article Proximal iterative Gaussian smoothing algorithm for a class of nonsmooth convex minimization problems

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

Chengxin Luo¹

1.
School of Mathematics and System Science, Shenyang Normal University, 253 Huanghei Northern Street, Shenyang, 110034

Received: December 2014

Revised: March 2015

Published: February 2015

Abstract Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90B35; Secondary: 47N10.

Citation:

Related Papers

Cited by

References

[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.