Parallel Machine Scheduling with Constraints in a Labelling Industry Case Study

This paper would present a case study on solving a parallel machine scheduling problem in the printing department of a global leader in labeling solutions. Motivated by low-season conditions with below-capacity order volumes, the study prioritizes accelerating job completions to reduce resource idle time in downstream processes. It would focus on minimizing the total weighted completion time while addressing real-world constraints including machine-job compatibility, shift boundaries, and resource limitations in color matching processes. The problem was formulated as a three parallel machines with different speeds model and used Weighted Shortest Processing Time dispatching rule to find out solutions. The scheduling objective is to minimize total weighted completion time. Our approach progressively incorporates operational constraints and achieves around 11.11% improvement in objective value compared to the current manual scheduling method. Some discussions on implementation of research results, limitations, and future optimization opportunities and real-time production data integration would be mentioned.

Parallel machine scheduling, Production constraints, Total weighted completion time, Dispatching rules, Weighted Shortest Processing Time rule

1. M. L. Pinedo, Scheduling: Theory, Algorithms, and Systems. New York: Springer, 2016. [Google Scholar] [Crossref]

2. J. Blazewicz, K. H. Ecker, E. Pesch, G. Schmidt, and J. Weglarz, Handbook on Scheduling: From Theory to Applications. Berlin: Springer, 2019. [Google Scholar] [Crossref]

3. K.C Ying, P. Pourhejazy, and X.Y. Huang, Revisiting the development trajectory of parallel machine scheduling, Computers & Operations Research, Volume 168, August 2024, 106709, Elsevier. [Google Scholar] [Crossref]

4. P. Baptiste, P. Brucker, S. Knust, and V. T'kindt, "Ten notes on equal-processing-time scheduling," 4OR, vol. 8, no. 4, pp. 355-371, 2010. [Google Scholar] [Crossref]

5. W. E. Smith, "Various optimizers for single-stage production," Naval Research Logistics Quarterly, vol. 3, no. 1-2, pp. 59-66, 1956. [Google Scholar] [Crossref]

6. E. Horowitz and S. Sahni, "Exact and approximate algorithms for scheduling nonidentical processors," Journal of the ACM, vol. 23, no. 2, pp. 317-327, 1976. [Google Scholar] [Crossref]

7. Allahverdi, C. T. Ng, T. C. E. Cheng, and M. Y. Kovalyov, "A survey of scheduling problems with setup times or costs," European Journal of Operational Research, vol. 187, no. 3, pp. 985-1032, 2008. [Google Scholar] [Crossref]

8. S. Kochhar and R. J. T. Morris, "Heuristic methods for flexible flow line scheduling," Journal of Manufacturing Systems, vol. 6, no. 4, pp. 299-314, 1987. [Google Scholar] [Crossref]

9. M. X. Weng, J. Lu, and H. Ren, "Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective," International Journal of Production Economics, vol. 70, no. 3, pp. 215-226, 2001. [Google Scholar] [Crossref]

• "Towards GDP to GEP-Centric Model: A Proposed GEP Index Framework and Its Application in Haryana"
• Physicochemical Analysis of Petroleum Products in Selected Depots in Calabar Metropolis Cross River State and The Effects on Motor Engine
• Impact of Employee Welfare Measures on Workforce Well-Being in SBI: Insights from the Public Banking Sector
• Problem of Small-Scale Farmers in Agricutlure Sector in Tirunelveli Taluk
• Globalization, Economic Development, and Ecological Footprint in Tunisia: A QARDL Approach