Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time

DOI10.1007/S001860300336MaRDI QIDQ706379zbMATH OpenOpenAlexFDO

Authors Philippe Baptiste, Vadim G. Timkovsky

Publication date 8 February 2005

Published in Mathematical Methods of Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s001860300336

zbMATH Keywords

complexityflow shopideal scheduleparallel machinesscheduling

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35)

Review text

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.

Recommendations

• scientific article; zbMATH DE number 2221458
• An efficient algorithm for finding ideal schedules
• Ideal preemptive schedules on two processors
• Two machine preemptive scheduling problem with release dates, equal processing times and precedence constraints
• A polynomial algorithm for \(P | p_j = 1,r_j, outtree\,| \sum C_j\)

Cited in

(11)

• A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
• Normal-form preemption sequences for an open problem in scheduling theory
• Ideal schedules in parallel machine settings
• How small are shifts required in optimal preemptive schedules?
• A new polynomial algorithm for a parallel identical scheduling problem
• scientific article; zbMATH DE number 4033467 (Why is no real title available?)
• Polynomial-time approximation schemes for scheduling problems with time lags
• Fast LP models and algorithms for identical jobs on uniform parallel machines
• An efficient algorithm for finding ideal schedules
• A fixed-parameter algorithm for scheduling unit dependent tasks on parallel machines with time windows
• A decomposition scheme for single stage scheduling problems

This page was built for publication: Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q706379)