.png){kind=icon}
.png){kind=icon}
Return
Scheduling problems on parallel machines with machine-dependent generalized due-dates
.png){kind=icon}
PRE
AI
DOI：10.1007/s10479-025-06468-0.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
In scheduling problems with generalized due-dates, the due-dates are position-dependent (and not job-dependent as in classical scheduling). In this paper, we study scheduling problems on parallel machines, and the underlying assumption is that the generalized due-dates are machine-dependent. The following scheduling measures are considered: total tardiness, maximum tardiness, number of tardy jobs, and total late work. We show that all the problems are NP-hard even if all generalized due-dates are identical. We complement this hardness result by showing that all problems are solvable in pseudo-polynomial time and that minimizing total late work is fixed parametrized tractable with respect to the number of different generalized due-dates and processing times in the instance. We also tested the pseudo-polynomial time algorithms, showing they can easily solve instances containing up to 200 jobs.
Keywords:
Scheduling
Parallel machines
Generalized due-dates
Dynamic programming
Fixed parametrized tractability
Journal
IF:
4.5
Papers:
8.0K
Citations:
2.1W