The Two-Stage Assembly Scheduling Problem: Complexity and Approximation

DOI10.1287/OPRE.43.2.346zbMath0837.90069OpenAlexW2044336241MaRDI QIDQ4849333

Chris N. Potts, Luk N. Van Wassenhove, C. M. Zwaneveld, Sergey Sevast'janov, Vitaly A. Strusevich

Publication date: 25 September 1995

Published in: Operations Research (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/5db58a1f020f4f21a9e63f698b0eea8fbd23fca7

zbMATH Keywords

makespanNP-hardtwo-stage assembly schedulingworst-case ratio bound

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35) Production models (90B30)

Related Items (60)

Scheduling for two-stage production system with setup and assembly operations ⋮ Deterministic assembly scheduling problems: a review and classification of concurrent-type scheduling models and solution procedures ⋮ Cyclic robot scheduling for 3D printer-based flexible assembly systems ⋮ Scheduling a hybrid assembly-differentiation flowshop to minimize total flow time ⋮ A branch-and-bound algorithm and four metaheuristics for minimizing total completion time for a two-stage assembly flow-shop scheduling problem with learning consideration ⋮ Optimization study of three-stage assembly flowshop problem in pharmacy automation dispensing systems ⋮ Two-stage three-machine assembly scheduling problem with sum-of-processing-times-based learning effect ⋮ Minimizing the total completion time in a distributed two stage assembly system with setup times ⋮ The 2-stage assembly flowshop scheduling problem with total completion time: efficient constructive heuristic and metaheuristic ⋮ On the two-stage hybrid flow shop with dedicated machines ⋮ Two-stage no-wait scheduling models with setup and removal times separated ⋮ Cloud theory-based simulated annealing approach for scheduling in the two-stage assembly flowshop ⋮ A self-adaptive differential evolution heuristic for two-stage assembly scheduling problem to minimize maximum lateness with setup times ⋮ A note on the complexity of the concurrent open shop problem ⋮ A note on the two-stage assembly flow shop scheduling problem with uniform parallel machines ⋮ Assembly flowshop scheduling problem: speed-up procedure and computational evaluation ⋮ Distributed assembly permutation flow-shop scheduling problem with sequence-dependent set-up times using a novel biogeography-based optimization algorithm ⋮ A biased‐randomized iterated local search for the distributed assembly permutation flow‐shop problem ⋮ An effective algorithm for flexible assembly job‐shop scheduling with tight job constraints ⋮ Flow shop scheduling problem with non-linear learning effects: a linear approximation scheme for non-technical users ⋮ Meta-Lamarckian-based iterated greedy for optimizing distributed two-stage assembly flowshops with mixed setups ⋮ Lot streaming for a two-stage assembly system in the presence of handling costs ⋮ Two-stage no-wait hybrid flowshop scheduling with inter-stage flexibility ⋮ Less is more: variable neighborhood search for integrated production and assembly in smart manufacturing ⋮ Two-stage assembly scheduling with batch setup times, time-dependent deterioration, and preventive maintenance activities using meta-heuristic algorithms ⋮ Concurrent flowshop scheduling to minimize makespan. ⋮ Minimizing the makespan for a two-stage three-machine assembly flow shop problem with the sum-of-processing-time based learning effect ⋮ Scheduling with centralized and decentralized batching policies in concurrent open shops ⋮ The two-stage assembly flow shop scheduling with an availability constraint: worst case analysis ⋮ Minimizing customer order lead-time in a two-stage assembly supply chain ⋮ Two-machine flowshop scheduling in a physical examination center ⋮ Flow-shop scheduling with setup and assembly operations ⋮ A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations ⋮ A scheduling problem to minimize total weighted tardiness in the two-stage assembly flowshop ⋮ Heuristics for an assembly flow-shop with non-identical assembly machines and sequence dependent setup times to minimize sum of holding and delay costs ⋮ Batching decisions for assembly production systems ⋮ The three-stage assembly flowshop scheduling problem ⋮ The production scheduling problem in a multi-page invoice printing system ⋮ Three-stage flow-shop scheduling with assembly operations to minimize the weighted sum of product completion times ⋮ A two-stage assembly-type flowshop scheduling problem for minimizing total tardiness ⋮ Three-stage assembly flow shop scheduling problem with a fixed maintenance period ⋮ TWO-STAGE FLOWSHOP SCHEDULING PROBLEMS WITH IDENTICAL AND BATCH PROCESSORS ⋮ On the two-stage assembly flow shop problem ⋮ Two-stage assembly scheduling problem for minimizing total tardiness with setup times ⋮ Heuristics for a two-stage assembly flowshop with bicriteria of maximum lateness and makespan ⋮ Polynomial time approximation algorithms for machine scheduling: Ten open problems ⋮ Flowshop-scheduling problems with makespan criterion: a review ⋮ The two-stage assembly scheduling problem to minimize total completion time with setup times ⋮ Méthode heuristique pour le problème de flow shop hybride avec machines dédiées ⋮ A branch and bound algorithm for the two-stage assembly scheduling problem ⋮ A heuristic hybrid framework for vector job scheduling ⋮ Heuristics for the two-stage job shop scheduling problem with a bottleneck machine ⋮ A branch and bound algorithm for a production scheduling problem in an assembly system under due date constraints ⋮ Flexible flow shop scheduling with uniform parallel machines ⋮ A PSO and a tabu search heuristics for the assembly scheduling problem of the two-stage distributed database application ⋮ Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times ⋮ A HYBRID TWO-STAGE FLOWSHOP SCHEDULING PROBLEM ⋮ A computational study of heuristics for two-stage flexible flowshops ⋮ Powerful heuristics to minimize makespan in fixed, 3-machine, assembly-type flowshop scheduling ⋮ A branch and bound algorithm to minimize the total weighted flowtime for the two-stage assembly scheduling problem

This page was built for publication: The Two-Stage Assembly Scheduling Problem: Complexity and Approximation