A no-wait flowshop scheduling problem with processing flexibility and transportation

Expand
  • 1. School of Management, Shanghai University, Shanghai 200444, China; 2. College of Sciences, Shanghai University, Shanghai 200444, China

Received date: 2015-11-27

  Online published: 2016-12-15

Abstract

This paper addresses the performance of scheduling algorithms for a two-stage no-wait flowshop scheduling problem with processing flexibility and transportation, where each stage has one machine. Each job, composed of two operations, must be processed through the two stages without waiting time. We propose two approximation algorithms. The first algorithm is list scheduling and the second schedules the jobs in non-decreasing order of the total processing time of each job's two operations. We show that the worst case ratio of the algorithms is no more than 5/2 and 2, respectively. At last, we conduct numerical experiments to compare the performance of the algorithms. For the cases with different value of the parameters, we generate several instances. For every instance, the ratio of the algorithm's objective value and the optimal solution's objective value is obtained. For each case, the maximum, minimum and average value of the instances' ratio are obtained to analyze the performance of the two algorithms.

Cite this article

ZHONG Weiya, MA Xiaoru . A no-wait flowshop scheduling problem with processing flexibility and transportation[J]. Operations Research Transactions, 2016 , 20(4) : 93 -101 . DOI: 10.15960/j.cnki.issn.1007-6093.2016.04.011

References

[1] Cardoen B, Demeulemeester E, Belien J. Operating room planning and scheduling: a literature review [J]. European Journal of Operational Reasearch, 2010, 201(3): 921-932.
[2] Augusto V, Xie X, Perdomo V. Operating theatre scheduling with patient recovery in both operating rooms and recovery beds [J]. Computers and Industrial Engineering, 2010, 58(2): 231-238.
[3] Gilmore P, Gomory R. Sequencing a one-state variable machine: a solvable case of the traveling salesman problem [J]. Operations Research, 1964, 12(5): 665-679.
[4] Sriskandarajah C, Ladet P. Some no-wait shops scheduling problems: complexity aspect [J]. European Journal of Operational Research, 1986, 24(3): 424-438.
[5] Glass C A, Gupta J N D, Potts C N. Two-machine no-wait flow shop scheduling with missing operations [J]. Mathematics of Operations Research, 1999, 24(4): 911-924.
[6] Hall N G, Sriskandarajah C. A survey of machine scheduling problems with blocking and no-wait in process [J]. Operations Research, 1996, 44(3): 510-525.
[7] Vairaktarakis G L, Lee C Y. Analysis of algorithms for two-stage flowshops with multi-processor task flexibility [J]. Naval Research Logistics, 2004, 51(2): 44-59.
[8] Kouvelis P, Vairaktarakis G. Flowshops with processing flexibility across production stages [J]. IIE Transaction, 1998, 30(8): 735-746.
[9] Pan J C H, Wu C L, Huang H C, et al. Coordinating scheduling with batch deliveries in a two-machine flow shop [J]. International Journal of Advanced Manufacturing Technology, 2009, 40(5): 607-616.
[10] Chen Z L. Integrated production and outbound distribution scheduling: review and extensions [J]. Operations Research, 2010, 58(1): 130-148.
Outlines

/