Polynomial Algorithm for Constructing Pareto-Optimal Schedules for Problem 1∣<em>r</em><sub>j</sub>∣<em>L</em><sub>max</sub>,<em>C</em><sub>max</sub>
In this chapter, we consider the single machine scheduling problem with given release dates, processing times, and due dates with two objective functions. The first one is to minimize the maximum lateness, that is, maximum difference between each job due date and its actual completion time. The seco...
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Capítulo de libro |
| Lenguaje: | inglés |
| Publicado: |
IntechOpen
2020
|
| Materias: | |
| Acceso en línea: | https://www.intechopen.com/chapters/73530 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| Sumario: | In this chapter, we consider the single machine scheduling problem with given release dates, processing times, and due dates with two objective functions. The first one is to minimize the maximum lateness, that is, maximum difference between each job due date and its actual completion time. The second one is to minimize the maximum completion time, that is, to complete all the jobs as soon as possible. The problem is NP-hard in the strong sense. We provide a polynomial time algorithm for constructing a Pareto-optimal set of schedules on criteria of maximum lateness and maximum completion time, that is, problem
1
∣
r
j
∣
L
max
,
C
max
, for the subcase of the problem:
d
1
≤
d
2
≤
…
≤
d
n
;
d
1
−
r
1
−
p
1
≥
d
2
−
r
2
−
p
2
≥
…
≥
d
n
−
r
n
−
p
n
. |
|---|---|
| ISBN: | 978-1-78984-718-5 |
| DOI: | 10.5772/intechopen.93677 |