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

DOI10.1016/S0025-5610(97)00097-XzbMATH Open0920.90076MaRDI QIDQ1290645FDOQ1290645

Gerhard J. Woeginger, Jack A. A. van der Veen, Shuzhong Zhang

Publication date: 3 June 1999

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

Recommendations

• The time-dependent traveling salesman problem and single machine scheduling problems with sequence dependent setup times
• scientific article; zbMATH DE number 3848953
• Publication:3481474
• Low-complexity algorithms for sequencing jobs with a fixed number of job-classes
• Single machine group scheduling with resource dependent setup and processing times

zbMATH Keywords

makespanone-machine schedulingasymmetric traveling salesmanpolynomial time solution algorithm

Mathematics Subject Classification ID

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

Cited In (9)

• New exact and heuristic algorithms to solve the prize-collecting job sequencing problem with one common and multiple secondary resources
• \(\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
• Sequencing situations with just-in-time arrival, and related games
• Scheduling multi-colour print jobs with sequence-dependent setup times
• A survey of scheduling problems with setup times or costs
• A 3/2-Approximation for the Metric Many-Visits Path TSP
• ILS heuristics for the single-machine scheduling problem with sequence-dependent family setup times to minimize total tardiness

This page was built for publication: Sequencing jobs that require common resources on a single machine: A solvable case of the TSP

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