Name
Title | ||
|---|---|---|
Alternative algorithms for identical machines scheduling to maximize total early work with a common due date |
Abstract | ||
|---|---|---|
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., Pm|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 approximation approaches are validated in the computational experiments. |
Year | DOI | Venue |
|---|---|---|
2022 | 10.1016/j.cie.2022.108386 | Computers & Industrial Engineering |
Keywords | DocType | Volume |
Identical machines scheduling,Early work maximization,Common due date,Dynamic programming,Fully polynomial time approximation scheme | Journal | 171 |
ISSN | Citations | PageRank |
0360-8352 | 0 | 0.34 |
References | Authors | |
0 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Chen Xin | 1 | 625 | 120.92 |
| Xuefeng Shen | 2 | 0 | 0.34 |
| Mikhail Y. Kovalyov | 3 | 1602 | 118.18 |
| Malgorzata Sterna | 4 | 0 | 0.34 |
| Jacek Blazewicz | 5 | 1064 | 154.23 |