Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time
type: Item
instance of: scholarly article
title: Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time
zbMATH Open document ID: 1083.90021
author: Philippe Baptiste
author: Vadim G. Timkovsky
published in: Mathematical Methods of Operations Research
publication date: 2005-02-08T00:00:00Z
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.
reviewed by: Sigrid Knust
Mathematics Subject Classification ID: 90B35
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 2132321
zbMATH Keywords: scheduling
zbMATH Keywords: complexity
zbMATH Keywords: parallel machines
zbMATH Keywords: flow shop
zbMATH Keywords: ideal schedule
MaRDI profile type: Publication
full work available at URL: s001860300336
OpenAlex ID: W2083845110
DOI: 10.1007/S001860300336
description: scientific article; zbMATH DE number 2132321