Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time (Q706379)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time |
scientific article; zbMATH DE number 2132321
| 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; zbMATH DE number 2132321 |
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
