A parallel machine scheduling problem maximizing total weighted early work

Byung Cheon Choi, Myoung Ju Park, Kyung Min Kim, Yunhong Min

Research output: Contribution to journalArticlepeer-review

1 Citation (Scopus)


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.

Original languageEnglish
Article number2150007
JournalAsia-Pacific Journal of Operational Research
Publication statusAccepted/In press - 2021


  • Approximation algorithm
  • Computational complexity
  • Early work
  • Scheduling


Dive into the research topics of 'A parallel machine scheduling problem maximizing total weighted early work'. Together they form a unique fingerprint.

Cite this