Premium
Scheduling and lot streaming in two‐machine open shops with no‐wait in process
Author(s) -
Hall Nicholas G.,
Laporte Gilbert,
Selvarajah Esaignani,
Sriskandarajah Chelliah
Publication year - 2005
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.20065
Subject(s) - travelling salesman problem , open shop , job shop scheduling , computer science , scheduling (production processes) , schedule , mathematical optimization , heuristic , open shop scheduling , product (mathematics) , process (computing) , sequence (biology) , operations research , flow shop scheduling , artificial intelligence , mathematics , algorithm , operating system , geometry , biology , genetics
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, 2005