Some complexity results in cyclic scheduling

DOI10.1016/0895-7177(94)90210-0zbMath0810.90071OpenAlexW2158408330MaRDI QIDQ1341404

V. Pereyra

Publication date: 11 January 1995

Published in: Mathematical and Computer Modelling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0895-7177(94)90210-0

zbMATH Keywords

makespanNP-hardjob-shopcyclic schedulingflow-shopflexible assembly line

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Deterministic scheduling theory in operations research (90B35)

Related Items (13)

Complexity of cyclic job shop scheduling problems for identical jobs with no-wait constraints ⋮ 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 ⋮ CROSS cyclic resource-constrained scheduling solver ⋮ High-multiplicity cyclic job shop scheduling ⋮ A cyclic approach to large-scale short-term planning in chemical batch production ⋮ Benders' decomposition for the balancing of assembly lines with stochastic demand ⋮ Periodic schedules for linear precedence constraints ⋮ Cyclic scheduling in 3-machine robotic flow shops ⋮ New multi-objective method to solve reentrant hybrid flow shop scheduling problem ⋮ On scheduling cycle shops: Classification, complexity and approximation ⋮ The complexity of cyclic shop scheduling problems

Cites Work

• Unnamed Item
• Unnamed Item
• Minimax algebra
• Dynamic analysis of repetitive decision-free discrete-event processes: The algebra of timed marked graphs and algorithmic issues
• Sequencing in an Assembly Line with Blocking to Minimize Cycle Time
• A linear-system-theoretic view of discrete-event processes and its use for performance evaluation in manufacturing
• On cyclic sequence types for constructing cyclic schedules
• A Guaranteed-Accuracy Round-off Algorithm for Cyclic Scheduling and Set Covering
• Flowshop scheduling with limited temporary storage
• Compact Cylindrical Chromatic Scheduling
• Cyclic Schedules for Job Shops with Identical Jobs
• The Economic Lot Scheduling Problem (ELSP): Review and Extensions
• Stochastic Analysis of Cyclic Schedules
• Performance Measures and Schedules in Periodic Job Shops
• Cyclic Scheduling in a Stochastic Environment
• On the General Feasibility Test of Scheduling Lot Sizes for Several Products on One Machine
• Sequencing a One State-Variable Machine: A Solvable Case of the Traveling Salesman Problem
• Cyclic scheduling in flow lines: Modeling observations, effective heuristics and a cycle time minimization procedure

This page was built for publication: Some complexity results in cyclic scheduling