Scheduling and lot streaming in two‐machine open shops with no‐wait in process
Authors:
- Nicholas G. HallNHNicholas G. Hall
- Chelliah SriskandarajahCSChelliah Sriskandarajah
- 3 February 2005
- journal article
- research article
- Published by Wiley in Naval Research Logistics (NRL)
- Vol. 52 (3) , 261-275
Abstract
We study the problem of minimizing the makespan in no‐wait two‐machine open shops producing multiple products using lot streaming. In no‐wait open shop scheduling, sublot sizes are necessarily consistent; i.e., they remain the same over all machines. This intractable problem requires finding sublot sizes, a product sequence for each machine, and a machine sequence for each product. We develop a dynamic programming algorithm to generate all the dominant schedule profiles for each product that are required to formulate the open shop problem as a generalized traveling salesman problem. This problem is equivalent to a classical traveling salesman problem with a pseudopolynomial number of cities. We develop and test a computationally efficient heuristic for the open shop problem. Our results indicate that solutions can quickly be found for two machine open shops with up to 50 products. © 2005 Wiley Periodicals, Inc. Naval Research Logistics, 2005Keywords
This publication has 15 references indexed in Scilit:
- Minimizing Cycle Time in a Blocking FlowshopOperations Research, 2000
- Basic Techniques for Lot StreamingOperations Research, 1993
- Chapter 9 Sequencing and scheduling: Algorithms and complexity1993
- Integrating Scheduling with Batching and Lot-Sizing: A Review of Algorithms and ComplexityJournal of the Operational Research Society, 1992
- Solution Procedures for the Lot‐Streaming ProblemDecision Sciences, 1990
- Flow shop scheduling with lot streamingOperations Research Letters, 1989
- Some New Branching and Bounding Criteria for the Asymmetric Travelling Salesman ProblemManagement Science, 1980
- Complexity of Scheduling Shops with No Wait in ProcessMathematics of Operations Research, 1979
- A Patching Algorithm for the Nonsymmetric Traveling-Salesman ProblemSIAM Journal on Computing, 1979
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979