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