Two-machine flow shop scheduling with a common due date to maximize total early work

Xin Chen, Qian Miao, Bertrand M.T. Lin*, Malgorzata Sterna, Jacek Błażewicz


研究成果: Article同行評審

6 引文 斯高帕斯(Scopus)


This paper considers scheduling in a two-machine flow shop to maximize the total early work subject to a common due date. The early work of a job is a parameter defined as the total amount of the job that is processed before the specified due date. We mainly focus on the unweighted model in this paper, and propose a dynamic programming approach running in time (compared with the previous result in time for the weighted case discussed in the literature). Then we analyse the problem from an approximation point of view, in which we first show that Johnson’s algorithm, one of the most classical ones in flow shop scheduling, can only achieve the worst performance ratio for the considered problem (although it is an optimal one for makespan minimization). With the motivation of proposing better approximation algorithms, we further design a fully polynomial time approximation scheme (FPTAS). Finally, we point out that the approximation results also work for the weighted model - if a specific constraint is satisfied.
原文American English
頁(從 - 到)504-511
期刊European Journal of Operational Research
出版狀態Published - 16 7月 2022


深入研究「Two-machine flow shop scheduling with a common due date to maximize total early work」主題。共同形成了獨特的指紋。