A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times

DOI10.1016/j.disopt.2013.07.003zbMath1506.90113OpenAlexW1977635807MaRDI QIDQ1799381

Nadia Brauner, Christophe Rapine

Publication date: 18 October 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2013.07.003

zbMATH Keywords

schedulingavailability constraintsmakespan criterion

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Related Items (3)

High-multiplicity scheduling on one machine with forbidden start and completion times ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Approximate and robust bounded job start scheduling for Royal Mail delivery offices

Cites Work

• Unnamed Item
• Parallel machine scheduling problems with a single server
• Parallel machine scheduling with multiple unloading servers
• Single machine scheduling with forbidden start times
• Operator non-availability periods
• One-operator-two-machine flowshop scheduling with setup and dismounting times
• Parallel machine scheduling with a common server
• Single machine scheduling with small operator-non-availability periods
• Scheduling two parallel semiautomatic machines to minimize machine interference
• A framework for the complexity of high-multiplicity scheduling problems
• Scheduling two parallel machines with a single server: the general case
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem

This page was built for publication: A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times