Abstract
In this paper, we investigate the single machine lot scheduling problem in which each lot contains one or more jobs (or part of jobs). Jobs with different sizes are splittable and should be processed in consecutive lots. Any completed (part of a) job is delivered to the customer on its completion. We generalize the problem studied in Zhang et al. (Inf Process Lett 142:46–51, 2019) such that lots may have different capacities and processing times, and the sizes of jobs are unbounded. We show that for this generalized case, the WSPT (Weighted Shortest Processing Time first) rule is still optimal for both minimizing total weighted completion time and minimizing total weighted discounted completion time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Coffman ED, Nozari A, Yannakakis M (1989) Optimal scheduling of products with two subassemblies on single machine. Oper Res 37:426–436
Dobson G, Karmarkar UD, Rummel JL (1989) Batching to minimize flow times on parallel heterogeneous machines. Manag Sci 35:607–613
Hou YT, Yang DL, Kuo WH (2014) Lot scheduling on a single machine. Inf Process Lett 114(12):718–722
Mor B (2020) Single-machine lot scheduling with variable lot processing times. Eng Optim. https://doi.org/10.1080/0305215X.2020.1722119
Mor B, Mosheiov G (2012) Batch scheduling of identical jobs on parallel identical machines. Inf Process Lett 112:762–766
Mosheiov G, Oron D, Ritov Y (2005) Minimizing flow-time on a single machine with integer batch sizes. Oper Res Lett 33:497–501
Naddef D, Santos C (1988) One-pass batching algorithms for the one-machine problem. Discrete Appl Math 21:133–145
Santos C, Magazine M (1985) Batching in single operation manufacturing systems. Oper Res Lett 4:99–103
Shallcross DF (1992) A polynomial algorithm for a one machine batching problem. Oper Res Lett 11:213–218
Yang DL, Hou YT, Kuo WH (2017) A note on a single-machine lot scheduling problem with indivisible orders. Comput Oper Res 79:34–38
Zhang E, Liu M, Zheng F et al (2019) Single machine lot scheduling to minimize the total weighted (discounted) completion time. Inf Process Lett 142:46–51
Acknowledgements
The authors are grateful to the referees for their valuable comments and suggestions. This work was partially supported by the National Natural Science Foundation of China under Grant No. 11771346.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Chen, Y., Cheng, Y. & Zhang, G. Single machine lot scheduling with non-uniform lot capacities and processing times. J Comb Optim 43, 1359–1367 (2022). https://doi.org/10.1007/s10878-020-00654-5
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-020-00654-5