No Access

A Parallel Machine Scheduling Problem Maximizing Total Weighted Early Work

School of Business, Chungnam National University, 99 Daehak-ro, Yuseong-gu, Daejeon 34134, Korea

Department of Industrial and Management Systems Engineering, Kyung Hee University, 1732, Deogyeong-daero, Giheung-gu, Yongin-si, Kyunggi-do 17104, Korea

E-mail Address: pmj0684@khu.ac.kr

Search for more papers by this author

Kyung Min Kim

Department of Industrial Management and Engineering, Myongji University, 116 Myongji-ro, Choein-gu, Yongin-si, Gyeonggido 17058, Korea

E-mail Address: kmkim@mju.ac.kr

Search for more papers by this author

, and

Yunhong Min

Graduate School of Logistics, Incheon National University, 119, Academy-ro, Yeonsu-gu, Incheon, Gyeonggi-do 22012, Korea

E-mail Address: yunhong.min@inu.ac.kr

Corresponding author.

Search for more papers by this author

https://doi.org/10.1142/S021759592150007XCited by:8 (Source: Crossref)

Abstract

We consider the total weighted early work maximization problem on identical machines in parallel such that the weights are identical, or the due date is the same. First, we present an approach to solve the case with a fixed number of machines in pseudo-polynomial time. Then, we develop approximation algorithms for the two cases with identical weights and with a common due date. For the case with identical weights, furthermore, we show that the parallel-machine and a single-machine cases are strongly NP-hard and weakly NP-hard, respectively, even if the due date of each job is equal to the processing time multiplied by a constant.

Keywords:

References

Blazewicz, J (1984). Scheduling preemptible tasks on parallel processors with information loss. Technique et Science Informatiques, 3(6), 415–420. Web of Science, Google Scholar
Blazewicz, J, K Ecker, E Pesch, G Schmidt, M Sterna and J Weglarz (2019). Handbook on Scheduling. From Theory to Practice, 2nd edn. Cham: Springer. Crossref, Google Scholar
Cheng, TCE and MC Gupta (1989). Survey of scheduling research involving due date determination decisions. European Journal of Operational Research, 38, 156–166. Crossref, Web of Science, Google Scholar
Chen, X, Y Liang, M Sterna, W Wang and J Blazewicz (2020). Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date. European Journal of Operational Research, 284(1), 67–74. Crossref, Web of Science, Google Scholar
Chen, X, M Sterna, X Han and J Blazewicz (2016). Scheduling on parallel identical machines with late work criterion: Offline and online cases. Journal of Scheduling, 19(6), 729–736. Crossref, Web of Science, Google Scholar
Chung, Y and M-J Park (2015). Notes on inverse bin-packing problems. Information Processing Letters, 115, 60–68. Crossref, Web of Science, Google Scholar
Graham, RL, EL Lawler, JK Lenstra and AHG Rinnooy Kan (1979). Optimization and approximation in deterministic sequencing and scheduling. Annals of Discrete Mathematics, 5, 287–326. Crossref, Google Scholar
Györgyi, P and T Kis (2020). A common approximation framework for early work, late work, and resource leveling problems. European Journal of Operational Research, 286(1), 129–137. Crossref, Web of Science, Google Scholar
Hariri, AMA, CN Potts and LN Van Wassenhove (1995). Single machine scheduling to minimize total weighted late work. ORSA Journal on Computing, 7(2), 232–242. Crossref, Google Scholar
Kovalyov, MY, CN Potts and LN Van Wassenhove (1994). A fully polynomial approximation scheme for scheduling a single machine to minimize total weighted late work. Mathematics of Operations Research, 19(1), 86–93. Crossref, Web of Science, Google Scholar
Li, W (2020). Improved approximation schemes for early work scheduling on identical parallel machines with common due date. arXiv:2007.12388. Google Scholar
Potts, CN and LN Van Wassenhove (1992). Single machine scheduling to minimize total late work. Operations Research, 40(3), 586–595. Crossref, Web of Science, Google Scholar
Sterna, M (2006). Late work scheduling in shop systems. Dissertations 405, Publishing House of Poznan University of Technology. Google Scholar
Sterna, M and K Czerniachowska (2017). Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work. Journal of Optimization Theory and Applications, 174(3), 927–944. Crossref, Web of Science, Google Scholar