Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time (Q706379): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
| Property / full work available at URL | |||
| Property / full work available at URL: https://doi.org/10.1007/s001860300336 / rank | |||
Normal rank | |||
| Property / OpenAlex ID | |||
| Property / OpenAlex ID: W2083845110 / rank | |||
Normal rank | |||
Latest revision as of 21:16, 19 March 2024
scientific article
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time |
scientific article |
Statements
Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time (English)
0 references
8 February 2005
0 references
In this paper two-machine scheduling problems with unit processing times, release dates, precedence constraints and minimum total completion time are studied. More specifically, it is shown that problems \(P2| prec,r_j,p_j=1| \sum C_j\) and \(F2| prec,r_j,p_j=1| \sum C_j\) are polynomially solvable by reducing them to shortest path problems. Furthermore, the concept of ideal schedules (minimizing the makespan and total completion time simultaneously) is discusssed.
0 references
scheduling
0 references
complexity
0 references
parallel machines
0 references
flow shop
0 references
ideal schedule
0 references
