.png){kind=icon}
.png){kind=icon}
Return
Maximum Lateness Minimization on Two-Parallel Machine with a Non-availability Interval
.png){kind=icon}
PRE
AI
DOI：10.1007/978-3-032-08381-4_13.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper addresses the problem of scheduling two identical parallel machines with a non-availability interval. The objective is to minimize the maximum lateness when each job has a positive tail, the problem is shown to have a constant polynomial-time approximation algorithm providing a significant theoretical framework for addressing such scheduling issues. A Dynamic Programming (DP) approach is proposed, and it is demonstrated that the problem has a Fully Polynomial Time Approximation Scheme (FPTAS) with a strongly polynomial running time. The results indicate that the FPTAS achieves solutions that closely approximate those of the DP, often yielding optimality within significantly reduced computational times. Additionally, the analysis highlights the substantial impact of processing time ranges and the position of the non-availability interval on the performance of the FPTAS.
Keywords:
Scheduling
Parallel machines
Maximum lateness
Dynamic Programming
FPTAS
Journal
M
IF:
0
Papers:
48
Citations:
0