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

DOI10.1007/S10951-016-0475-ZzbMATH Open1353.90059OpenAlexW2331986476MaRDI QIDQ341471FDOQ341471

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

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

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)

Cites Work

• Single machine scheduling with small operator-non-availability periods
• Integer Programming with a Fixed Number of Variables
• Strongly Polynomial Algorithms for the High Multiplicity Scheduling Problem
• Fast integer programming in fixed dimension
• Exact and approximate algorithms for high-multiplicity parallel machine scheduling
• Operator non-availability periods
• A framework for the complexity of high-multiplicity scheduling problems
• Complexity and approximation of single machine scheduling with an operator non-availability period to minimize total completion time
• Parallel machine scheduling with high multiplicity
• Single machine scheduling with forbidden start times
• 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

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)