Scheduling and lot streaming in two‐machine open shops with no‐wait in process Academic Article uri icon


  • 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.

author list (cited authors)

  • Hall, N. G., Laporte, G., Selvarajah, E., & Sriskandarajah, C.

citation count

  • 6

complete list of authors

  • Hall, Nicholas G||Laporte, Gilbert||Selvarajah, Esaignani||Sriskandarajah, Chelliah

publication date

  • April 2005