The complexity of cyclic shop scheduling problems

DOI10.1002/jos.100zbMath1009.90048OpenAlexW2012996261WikidataQ58199815 ScholiaQ58199815MaRDI QIDQ1607980

Tae-Eog Lee, Nicholas G. Hall, Marc E. Posner

Publication date: 8 August 2002

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

Full work available at URL: https://doi.org/10.1002/jos.100

zbMATH Keywords

complexityalgorithmsmanufacturingsequencingcyclic scheduling

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35) Production models (90B30) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (17)

Cyclic hoist scheduling in large real-life electroplating lines ⋮ A branch and bound algorithm for the cyclic job-shop problem with transportation ⋮ Complexity of cyclic job shop scheduling problems for identical jobs with no-wait constraints ⋮ Tabu search algorithms for cyclic machine scheduling problems ⋮ On the connection between a cyclic job shop and a reentrant flow shop scheduling problem ⋮ Minimizing flow time in cyclic schedules for identical jobs with acyclic precedence: The bottleneck lower bound. ⋮ A graph-based analysis of the cyclic scheduling problem with time constraints: schedulability and periodicity of the earliest schedule ⋮ Construction of cyclic schedules in presence of parallel machines ⋮ Medium term production management for cyclic deliveries ⋮ Linear programming-based algorithms for the minimum makespan high multiplicity jobshop problem ⋮ On the geometry, preemptions and complexity of multiprocessor and shop scheduling ⋮ Minimizing the cycle time of multiple-product processing networks with a fixed operation sequence, setups, and time-window constraints ⋮ Minimizing the number of workers in a paced mixed-model assembly line ⋮ Open shop cyclic scheduling ⋮ High-multiplicity cyclic job shop scheduling ⋮ An algorithm for the maximum revenue jobshop problem ⋮ Throughput-optimal sequences for cyclically operated plants

Cites Work

• Unnamed Item
• Unnamed Item
• V-shop scheduling
• The complexity of scheduling jobs in repetitive manufacturing systems
• Study of a NP-hard cyclic scheduling problem: The recurrent job-shop
• Some complexity results in cyclic scheduling
• Optimal two- and three-stage production schedules with setup times included
• Sequencing in an Assembly Line with Blocking to Minimize Cycle Time
• Cyclic Schedules for Job Shops with Identical Jobs
• Flowshop and Jobshop Schedules: Complexity and Approximation
• The Complexity of Flowshop and Jobshop Scheduling
• Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
• Performance Measures and Schedules in Periodic Job Shops
• Cyclic Scheduling in a Stochastic Environment
• Minimizing Makespan in a Class of Reentrant Shops
• A Survey of Machine Scheduling Problems with Blocking and No-Wait in Process

This page was built for publication: The complexity of cyclic shop scheduling problems