We study the early work scheduling problem on identical parallel machines in order to maximize the total early work, i.e., the parts of non-preemptive jobs that are executed before a common due date. By preprocessing and constructing an auxiliary instance which has several good properties, for any desired accuracy ε, we propose an efficient polynomial time approximation scheme with running time O (f (1/ε) n), where n is the number of jobs and f (1/ε) is exponential in 1/ε, and a fully polynomial time approximation scheme with running time O (1/ε2m+1 + n) when the number of machines is fixed.
Wei-Dong Li
. Improved Approximation Schemes for Early Work Scheduling on Identical Parallel Machines with a Common Due Date[J]. Journal of the Operations Research Society of China, 2024
, 12(2)
: 341
-350
.
DOI: 10.1007/s40305-022-00402-y
[1] Chen, X., Liang, Y., Sterna, M., Wang, W., Bła· zewicz, J.:Fully polynomial time approximation scheme to maximize early work on parallel machines with common due date. Eur. J. Oper. Res. 284(1), 67-74(2020)
[2] Sterna, M., Czerniachowska, K.:Polynomial time approximation scheme for two parallel machines scheduling with a common due date to maximize early work. J. Optimiz. Theory. App. 174, 927-944(2017)
[3] Sterna, M.:A survey of scheduling problems with late work criteria. Omega 39(2), 120-129(2011)
[4] Chen, X., Wang, W., Xie, P., Zhang, X., Sterna, M., Bła· zewicz, J.:Exact and heuristic algorithms for scheduling on two identical machines with early work maximization. Comput. Ind. Eng. 144, 106449(2020)
[5] Györgyi, P., Kis, T.:A common approximation framework for early work, late work, and resource leveling problems. Eur. J. Oper. Res. 286(1), 129-137(2020)
[6] Chen, X., Sterna, M., Han, X., Bła· zewicz, J.:Scheduling on parallel identical machines with late work criterion:offline and online cases. J. Sched. 19, 729-736(2016)
[7] Chen, X., Kovalev, S., Liu, Y., Sterna, M., Chalamon, I., Bła· zewicz, J.:Semi-online scheduling on two identical machines with a common due date to maximize total early work. Discrete. Appl. Math.(2020). https://doi.org/10.1016/j.dam.2020.05.023
[8] Lenstra, H.W., Jr.:Integer programming with a fixed number of variables. Math. Oper. Res. 8(4), 538-548(1983)
