Two parallel-machine scheduling with maximum waiting time for an emergency job

Abstract

In modern manufacturing and service industries, urgent orders and service tasks are common, and the speed of handling such urgent tasks is an important indicator of production and service efficiency. In this study, we consider scheduling jobs on two parallel machines with the random arrival of an emergency job. The objective is to minimise the makespan, subject to a given maximum waiting time of the emergency job. We first show that the worst-case ratio of the existing algorithm LPT${}_l$-SPT${}_{m-l}$ is at least 3/2 when m = 2. We then analyse some properties of the optimal schedule and derive lower bounds on the optimal makespan. Finally, we present an improved approximation algorithm with a tight worst-case ratio of 4/3. We also provide numerical results showing that our proposed algorithm outperforms algorithm LPT${}_l$-SPT${}_{m-l}$.

Keywords:

• Parallel machines
• emergency job
• makespan
• approximation algorithm

Disclosure statement

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

Data availability statement

The authors confirm that the data supporting the findings of this study are available within the article. All used data is provided in the paper. If readers have any question about the data used in this research, they are invited to contact the corresponding author who will share all available information.

Additional information

Funding

This research was supported in part by the Zhejiang Provincial Natural Science Foundation of China under grant number LZ23G010001, LY21G010002; National Natural Science Foundation of China under grant numbers 11971434; and the Contemporary Business and Trade Research Center of Zhejiang Gongshang University, which is a key Research Institute of Social Sciences and Humanities of the Ministry of Education of China. Cheng was supported in part by The Hong Kong Polytechnic University under the Fung Yiu King – Wing Hang Bank Endowed Professorship in Business Administration.

Notes on contributors

Yiwei Jiang

Yiwei Jiang is currently Full Professor at Zhejiang Gongshang University. His major research interests are in scheduling theory, supply chain management, approximation algorithms and online algorithms for combinatorial optimization problem. His papers have been published in journals such as Naval Research Logistics, European Journal of Operational Research, Information Sciences, Computers & Industrial Engineering, and so on.

Haodong Yuan

Haodong Yuan received his MPhil degree from the School of Management and E-Business at Zhejiang Gongshang University in January 2022. His research interests are scheduling and approximation algorithm.

Ping Zhou

Ping Zhou is Lecturer at College of Humanities, Zhejiang Business College. Her current research interests include scheduling theory and approximation algorithms. She has published articles in journals including Journal of Combinatorial Optimization, Theoretical Computer Science, Asia-Pacific Journal of Operational Research and so on.

T. C. E. Cheng

T. C. E. Cheng is Dean of PolyU Business School, Fung Yiu King – Wing Hang Bank Professor in Business Administration and Chair Professor of Management at The Hong Kong Polytechnic University. His research interests are in Operations Management and Operations Research. He has published over 1000 SCI/SSCI papers in journals such as Management Science, Operations Research, and Production and Operations Management, and co-authored 16 books.

Min Ji

Min Ji is currently Vice Dean and Full Professor of School of Management and E-Business at Zhejiang Gongshang University. His research interests are in scheduling, combinatorial optimization, approximation algorithm and computational complexity. His papers have been published in journals such as Naval Research Logistics, European Journal of Operational Research, International Journal of Production Economics, Computers & Operations Research and so on.