High-multiplicity scheduling on one machine with forbidden start and completion times

DOI10.1007/S10951-016-0475-ZMaRDI QIDQ341471zbMATH OpenOpenAlexFDO

Authors Michaël Gabay, Christophe Rapine, Nadia Brauner

Publication date 16 November 2016

Published in Journal of Scheduling (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10951-016-0475-z

zbMATH Keywords

schedulingparameterized complexityavailability constraintshigh-multiplicity

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Recommendations

• A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times
• Single machine scheduling with forbidden start times
• SINGLE MACHINE SCHEDULING WITH FORBIDDEN INTERVALS AND JOB DELIVERY TIMES
• Parallel machine scheduling with high multiplicity
• Two-agent single machine scheduling with forbidden intervals

Cites work

• A framework for the complexity of high-multiplicity scheduling problems
• A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times
• An asymptotically exact algorithm for the high-multiplicity bin packing problem
• Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time
• Exact and approximate algorithms for high-multiplicity parallel machine scheduling
• Fast integer programming in fixed dimension
• Integer Programming with a Fixed Number of Variables
• Operator non-availability periods
• Parallel machine scheduling with high multiplicity
• Single machine scheduling with forbidden start times
• Single machine scheduling with small operator-non-availability periods
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem

Cited in

(4)

• Parameterized complexity of machine scheduling: 15 open problems
• Approximate and robust bounded job start scheduling for Royal Mail delivery offices
• Single machine scheduling with forbidden start times
• A polynomial time algorithm for makespan minimization on one machine with forbidden start and completion times

This page was built for publication: High-multiplicity scheduling on one machine with forbidden start and completion times

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