Multitasking scheduling with job switching allowed between alternate periods

Abstract

This paper explores the multitasking scheduling problem via alternate periods, which is common in manufacturing and service industries. The shift pattern comprises regular shifts interspersed with breaks, allowing job switching. We focus on two alternate periods consisting of odd periods and even periods. Each job is not only processed completely within odd periods or completely within even periods, but job switching is also allowed between alternate periods with additional overhead. For this problem, we propose two job switching models. The first model is alternate periods multitasking scheduling with switching time, where a fixed switching time is incurred whenever a job is switched from one period to its adjacent period. The second model is alternate periods multitasking scheduling with diverse speeds, where an urgent switching cost is produced if a job is processed through the alternate periods with different speeds. For the two models, we study three scheduling objectives including minimising the total completion time, minimising the maximum lateness, and minimising the number of tardy jobs, respectively. For each of the problems under consideration, we investigate the structural properties of the optimal schedule and develop the corresponding pseudo-polynomial time dynamic programming algorithm. Furthermore, we give examples to effectively illustrate the proposed algorithms.

Keywords:

• Scheduling
• multitasking
• alternate period
• job switching
• dynamic programming

Acknowledgements

The authors are deeply grateful to the editor and the four anonymous reviewers for their instructive comments on the article.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Data availability statement

Data sharing is not applicable to this article as no new data were created or analysed in this study.

Additional information

Funding

This work is supported by the National Natural Science Foundation of China [Grant Nos.71931007 and 52075453], the Youth Foundation of Humanities and Social Sciences of Ministry of Education of China [Grant No. 23YJCZH227], the Chongqing Municipality Natural Science Foundation of China [Grant No. 2023NSCQ-MSX3822], and the Humanities and Social Sciences Program of Chongqing Municipality [Grant No. 23SKJD079].

Notes on contributors

Yan Wang

Yan Wang is a researcher at the School of Economics and Management, Chongqing Jiaotong University, China. Her research interests include the design and analysis of optimisation algorithms, multitasking scheduling, and operations research. Her work has appeared in Omega and Computers & Industrial Engineering.

Jun-Qiang Wang

Jun-Qiang Wang is a Professor with the Department of Industrial Engineering, School of Mechanical Engineering, Northwestern Polytechnical University (NPU), Xi'an, China. He is the Director of Performance Analysis Center of Production and Operations Systems (PacPos). He received his Ph.D. degree from the School of Mechanical Engineering of NPU in 2006. His research interests include modelling, planning, scheduling, analysis, and control of production and operations systems.

Yumei Huo

Yumei Huo is a Professor at CUNY, College of Staten Island and The Graduate Center. Her research interests include Design and Analysis of Algorithms, Sequence and Scheduling, Combinatorial Optimization, and Operations Research.