Alternative algorithms for identical machines scheduling to maximize total early work with a common due date

Xin Chen; Xuefeng Shen; Mikhail Y. Kovalyov; Małgorzata Sterna; Jacek Błażewicz

doi:10.1016/j.cie.2022.108386

Scientific Information System of the Poznań University of Technology

PL EN

Main page / Publications / Alternative algorithms for identical machines scheduling to maximize total early work with a common due date

Submit a comment

Article

Download BibTeX

Title

Alternative algorithms for identical machines scheduling to maximize total early work with a common due date

Authors

Xin Chen
Xuefeng Shen
Mikhail Y. Kovalyov
Małgorzata Sterna (WIiT) ^{[ 1 ][ 2.3 ][ P ]}
Jacek Błażewicz (WIiT) ^{[ 1 ][ 2.3 ][ P ]}

^{[ 1 ]} Instytut Informatyki, Wydział Informatyki i Telekomunikacji, Politechnika Poznańska | ^{[ P ]} employee

Scientific discipline (Law 2.0)

[2.3] Information and communication technology

Year of publication

2022

Published in

Computers & Industrial Engineering

Journal year: 2022 | Journal volume: vol. 171

Article type

scientific article

Publication language

english

Keywords

EN

Identical machines scheduling
Early work maximization
Common due date
Dynamic programming
Fully polynomial time approximation scheme

Abstract

EN We study a scheduling problem with a given number of identical parallel machines, a common job due date and the total early work criterion, i.e., P m|dj =d| max{X}, which is known to be NP-hard. A new dynamic programming algorithm is proposed, which is more efficient than the existing exact approach for this problem. Based on the proposed dynamic programming, we further design two new fully polynomial time approximation schemes. The effectiveness and efficiency of the new exact and pproximation approaches are validated in the computational experiments.

Date of online publication

01.07.2022

Pages (from - to)

108386-1 - 108386-9

DOI

10.1016/j.cie.2022.108386

URL

https://www.sciencedirect.com/science/article/abs/pii/S0360835222004296?via%3Dihub

Comments

Article Number: 108386

Ministry points / journal

140