Abstract
Scheduling models that allow the handling of pre-operational setup have been a source of major interests because of their practical relevance and theoretical impacts. Two-stage flow-lines have drawn much attention to researchers as they are simple, yet practical and can be easily extended to represent more complex situations. In this paper, two-machine flow-shop problems with a single setup server are surveyed. These problems have been shown to be NP-complete with special cases that are polynomial-time solvable. Several heuristics are proposed to solve the problems in general case, including simulated annealing, Tabu search, genetic algorithms, GRASP, and other hybrids. The results on small inputs are compared with the optimal solutions and results on large inputs are compared to a lower bound. Experiments show that the heuristics developed, obtain nearly optimal solutions.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Abdekhodaee, A. H. and A. Wirth, ‘Scheduling parallel machines with a single server: Some solvable cases and heuristics,’ Computers and Operations Research 29(3), 295–315 (2002).
Ben-Daya, M. and M. Al-Fawzan, ‘A tabu search approach for the flow-shop scheduling problem,’ European Journal of Operational Research 109(l), 88–95 (1998).
Brucker, P., S. Knust, and G. Wang, ‘Complexity results for flow-shop problems with a single server,’ OSM Reihe P, Heft 237, (2001).
Chen, C. L., V. S. Vempati, and N. Aljaber, ‘An application of genetic algorithms for flow-shop problems,’ European Journal of Operational Research 80(2), 389–396 (1995).
Cheng, T. C. E., G. Wang, and C. Sriskandarajah, ‘One-operator two-machine flow-shop scheduling with setup and dismounting times,’ Computers and Operations Research 26(7), 715–730 (1999).
Garey, M. R., D. S. Johnson, and R. Sethi, ‘The complexity of flowshop and jobshop scheduling,’ Mathematics of Operations Research 1(2), 117–128 (1974).
Glass, C. A., Y. M. Shafransky, and V. A. Strusevich, ‘Scheduling for parallel dedicated machines with a single server,’ Naval Research Logistics 47, 304–328 (2000).
Glover, F., ‘Tabu Search-Part I,’ ORSA Journal on Computing 1(3), 190–206 (1989).
Glover, F., ‘Tabu Search-Part II,’ ORSA Journal on Computing 2(1), 4–32 (1990).
Goldberg, D. E., Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1989.
Gupta, J. N. D., ‘Two-stage, hybrid flowshop scheduling problem,’ Journal of Operational Research Society 39, 359–364 (1988).
Gupta, J. N. D. and W. P. Darrow, ‘The Two-Machine Sequence Dependent Flowshop Scheduling Problem,’ European Journal of Operational Research, 439–446 (1986).
Holland, J., Adaptation in Nature and Artificial Systems, University of Michigan Press, Ann Arbor, MI, USA, 1975.
Ishibuchi, H., S. Misaki, and H. Tanaka, ‘Modified simulated annealing algorithms for the flow-shop sequencing problem,’ European Journal of Operational Research 81(2), 388–398, (1995).
Johnson, S. M., ‘Optimal two- and three-stage production schedules with set-up times included,’ Naval Research Logistics Quarterly 1(l), 61–68 (1954).
Krajeswski, L. J. and L. P. Ritzman, Operations Management: Strategy and Analysis, Reading, MA: Addison-Wesley, 1987.
Laarhoven, P. J. M. and E. H. L. Aarts, Aarts, Simulated Annealing: Theory and Applications, Kluwer Academic Publishers, Norwell, MA, 1987.
Narasimhan, S. L. and S. S. Panwalkar, ‘Scheduling in a two-stage manufacturing process,’ International Journal of Production Research 22, 555–564 (1984).
Murata, T., H. Ishibuchi, and H. Tanaka, ‘Genetic Algorithms for Flowshop Scheduling Problems,’ Computer and Industrial Engineering 30(4), 1061–1071 (1996).
Ogbu, F. A. and D. K. Smith, ‘The application of the simulated annealing algorithm to the solution of the n/m/Cmax flowshop problem,’ Computers and Operations Research 17(3), 243–253 (1990a).
Ogbu, F. A. and D. K. Smith, ‘Simulated annealing for the permutation flowshop problem,’ OMEGA 19(1), 64–67 (1990b).
Oliver, I., D. Smith, and J. Holland, ‘Simulated Annealing for the permutation flowshop scheduling,’ OMEGA 19, 64–67 (1987).
Osman, I. H. and C. N. Potts., ‘Simulated Annealing for Permutation Flow-Shop Scheduling,’ OMEGA 17(6), 551–557 (1989).
Resende, M. G. C. and C. C. Ribeiro, ‘Greedy Randomized Adaptive Search Procedures,’ AT&T Labs Research Technical Report TD-53RSJY, version, 2 (2002).
Taillard, E. D., ‘Some Efficient Heuristic Methods for the Flow Shop Sequencing Problem,’ European Journal of Operational Research 47(1), 65–74 (1990).
Taillard, E. D., ‘Parallel Taboo Search Techniques for the Job Shop Scheduling Problem,’ ORSA Journal on Computing 6(2), 108–117 (1994).
Widmer, M. and A. Hertz, ‘A new heuristic method for the flow-shop sequencing problem,’ European Journal of Operational Research 41(2), 186–193 (1989).
Yamada, T. and C. R. Reeves, ‘Permutation flowshop scheduling by genetic local search,” Proceedings of Second International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications (GALESIA′97),’ Institution of Electrical Engineers London, 232–238 (1997).
Yamada, T. and C. R. Reeves, ‘Genetic Algorithms, Path Relinking and the Flowshop Sequencing Problem,’ Evolutionary Computation journal (MIT press), 6(1), 230–234 (1998b).
Yoshida, T. and K. Hitomi, ‘Optimal two-stage production scheduling with setup times separated,’ AIIE Transactions 11, 261–263 (1979).
Zegordi, S. H., K. Itoh, and T. Enkawa, ‘Minimizing makespan for flow-shop scheduling by combining simulated annealing with sequencing knowledge,’ European Journal of Operational Research 85(3), 515–531 (1995).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Lim, A., Rodrigues, B. & Wang, C. Two-machine flow shop problems with a single server. J Sched 9, 515–543 (2006). https://doi.org/10.1007/s10951-006-8787-z
Issue Date:
DOI: https://doi.org/10.1007/s10951-006-8787-z