Sequencing jobs that require common resources on a single machine: A solvable case of the TSP

DOI10.1016/S0025-5610(97)00097-XzbMath0920.90076MaRDI QIDQ1290645

Gerhard J. Woeginger, Jack A. A. van der Veen, Shu-Zhong Zhang

Publication date: 3 June 1999

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

makespanone-machine schedulingasymmetric traveling salesmanpolynomial time solution algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items

A 3/2-Approximation for the Metric Many-Visits Path TSP, Sequencing situations with just-in-time arrival, and related games, ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness, A survey of scheduling problems with setup times or costs, \(\mathrm{A}^\ast\) search for prize-collecting job sequencing with one common and multiple secondary resources, \( \mathrm{A}^*\) -based construction of decision diagrams for a prize-collecting scheduling problem, Job sequencing with one common and multiple secondary resources: an A*/beam search based anytime algorithm, Scheduling multi-colour print jobs with sequence-dependent setup times, New exact and heuristic algorithms to solve the prize-collecting job sequencing problem with one common and multiple secondary resources