Abstract
In this paper we study the single-machine batch scheduling problem under batch availability, where both setup and job processing times are controllable by allocating a continuously divisible nonrenewable resource. Under batch availability a set of jobs is processed contiguously and completed together, when the processing of the last job in the batch is finished. We present polynomial time algorithms to find the job sequence, the partition of the job sequence into batches and the resource allocation, which minimize the total completion time or the total production cost (inventory plus resource costs).
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.References
Armstrong, R., Gu, S., & Lei, L. (1995). An algorithm for the two-resource allocation problem with a non-differentiable convex objective function. Journal of the Operational Research Society, 46, 116–122.
Armstrong, R., Gu, S., & Lei, L. (1997). Solving a class of two-resource allocation problems by equivalent load method. Journal of the Operational Research Society, 48, 818–825.
Cheng, T. C. E., & Kovalyov, M. Y. (1995). Single machine batch scheduling with deadlines and resource dependent processing times. Operations Research Letters, 17, 243–249.
Cheng, T. C. E., Janiak, A., & Kovalyov, M. Y. (2001). Single machine batch scheduling with resource dependent setup processing times. European Journal of Operational Research, 135, 177–183.
Coffman, E. G., Yannakakis, J. M., Magazine, M. J., & Santos, C. (1990). Batch sizing and job sequencing on a single machine. Annals of Operations Research, 26, 135–147.
Daniels, R. L. (1990). A multi-objective approach to resource allocation in single machine scheduling. European Journal of Operational Research, 48, 226–241.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Rinnooy Kan, A. H. G. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 3, 287–326.
Janiak, A. (1987). One-machine scheduling with allocation of continuously-divisible resource and with no precedence constraints. Kybernetika, 23(4), 289–293.
Janiak, A. (1989). Minimization of the blooming mill standstills—mathematical model, suboptimal algorithms. Mechanika, 8(2), 37–49.
Janiak, A., & Kovalyov, M. Y. (1996). Single machine scheduling subject to deadlines and resource dependent processing times. European Journal of Operational Research, 94, 284–291.
Monma, C. L., Schrijver, A., Todd, M. J., & Wei, V. K. (1990). Convex resource allocation problems on directed acyclic graphs: duality, complexity, special cases and extensions. Mathematics of Operations Research, 15, 736–748.
Ng, C. T. D., Cheng, T. C. E., & Kovalyov, M. Y. (2004). Single machine batch scheduling with jointly compressible setup and processing times. European Journal of Operational Research, 153, 211–219.
Nowicki, E., & Zdrzalka, S. (1990). A survey of results for sequencing problems with controllable processing times. Discrete Applied Mathematics, 26, 271–287.
Panwalkar, S. S., & Rajagopalan, R. (1992). Single machine sequencing with controllable processing times. European Journal of Operational Research, 59, 298–302.
Potts, C. N., & Van Wassenhove, L. (1991). Integrated scheduling with batching and lot-sizing: a review of algorithms and complexity. Journal of Operational Research Society, 43, 395–406.
Potts, C. N., & Kovalyov, M. Y. (2000). Scheduling with batching: a review. European Journal of Operational Research, 120, 228–249.
Scott, S. C., & Jefferson, T. R. (1995). Allocation of resources in project management. International Journal of Systems Science, 26(2), 413–420.
Shabtay, D. (2004). Single and a two-resource allocation algorithms for minimizing the maximal lateness in a single machine-scheduling problem. Computers and Operations Research, 31(8), 1303–1315.
Webster, K. R., & Baker, K. R. (1995). Scheduling groups of jobs on a single machine. Operations Research, 43, 692–703.
Vickson, R. G. (1980). Two single machine sequencing problems involving controllable job processing times. AIIE Transactions, 12(3), 258–262.
Van Wassenhove, L., & Baker, K. R. (1982). A bicriterion approach to time/cost trade-offs in sequencing. European Journal of Operational Research, 11, 48–54.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Shabtay, D., Steiner, G. Single machine batch scheduling to minimize total completion time and resource consumption costs. J Sched 10, 255–261 (2007). https://doi.org/10.1007/s10951-007-0025-9
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-007-0025-9