A Heuristic Based On Makespan Lower Bounds in Flow Shops with Multiple Processors

Vikram Srinivasan, Daryl Santos

Abstract


Minimum makespan scheduling of Flow Shops with Multiple Processors (FSMPs), also known as the Hybrid Flow Shop (HFS), is classified as NP complete. Thus, the FSMP largely depends on strong heuristics to develop solutions to makespan scheduling instances. An FSMP consists of m stages wherein each stage has one or more processors through which n jobs are scheduled. This paper presents a heuristic based on the lower bound developed in a prior work in order to determine good makespan solutions in the FSMP environment. In the environment studied in this work, the multiple machines available at a particular processing stage are identical processors. In order to evaluate the proposed heuristic, its performance is compared to makespans obtained via the use of modified pure flow shop heuristics. Results show that the proposed heuristic is indeed a strong heuristic for the FSMP and it provides makespans that are better than those provided by some of the already existing pure flow shop heuristics that have been adapted for the FSMP environment.

Full Text:

PDF

References


Brah S.A. (1988). Scheduling in a Flow Shop with Multiple Processors. unpublished Ph.D. dissertation, University of Houston, Houston, TX.

Brah, S. A., Santos, D. L., & Hunsucker, J. L. (1989). Heuristic programming study of a flow shop with multiple processors scheduling. In ORSA/TIMS Joint National Meeting, New York City.

Brah, S. A., & Hunsucker, J. L. (1991). Branch and bound algorithm for the flow shop with multiple processors. European journal of operational research, 51(1), 88-99.

Brah, S. A., & Wheeler, G. E. (1998). Comparison of scheduling rules in a flow shop with multiple processors: A simulation. Simulation, 71(5), 302-311.

Campbell, H. G., Dudek, R. A., & Smith, M. L. (1970). A heuristic algorithm for the n job, m machine sequencing problem. Management science, 16(10), B-630.

Edwards C., & Santos D.L. (2016). Efficacy of the NEH Heuristic in a Hybrid Flow Shop Environment, Proceedings of the 2016 Annual World Conference of the Society for Industrial and Systems Engineering, Bay Area, CA, October.

Garey M.R., & Johnson D.S. (1979). Computers and Intractability: A guide to the theory of NP-Completeness. San Francisco, Freeman Press.

Ho, J. C., & Chang, Y. L. (1991). A new heuristic for the n-job, M-machine flow-shop problem. European Journal of Operational Research, 52(2), 194-202.

Hunsucker, J. L., & Shah, J. R. (1994). Comparative performance analysis of priority rules in a constrained flow shop with multiple processors environment. European Journal of Operational Research, 72(1), 102-114.

Johnson, S. M., (1954). Optimal two‐and three‐stage production schedules with setup times included. Naval Research Logistics (NRL), 1(1), 61-68.

Montgomery D.C. (2006). Design and Analysis of Experiments. 5th edition. ISBN 9971-51-329-3.

Nawaz, M., Enscore, E. E., & Ham, I. (1983). A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem. Omega, 11(1), 91-95.

Palmer, D. S. (1965). Sequencing jobs through a multi-stage process in the minimum total time—a quick method of obtaining a near optimum. Journal of the Operational Research Society, 16(1), 101-107.

Pinedo, M. L. (2012). Scheduling: Theory, Algorithms, and Systems. New York: Springer.

Ruiz, R., & Vázquez-Rodríguez, J. A. (2010). The hybrid flow shop scheduling problem. European Journal of Operational Research, 205(1), 1-18.

Santos, D. L., Hunsucker, J. L., & Deal, D. E. (1995). Global lower bounds for flow shops with multiple processors. European journal of operational research, 80(1), 112-120.

Santos, D. L., Hunsucker, J. L., & Deal, D. E. (1996). An evaluation of sequencing heuristics in flow shops with multiple processors. Computers & Industrial Engineering, 30(4), 681-691.

Santos, D. L., Hunsucker, J. L., & Deal, D. E. (2001). On makespan improvement in flow shops with multiple processors. Production Planning & Control, 12(3), 283-295.

Younes N., Santos D.L., & Maria A. (1998). A Simulated Annealing Approach to Scheduling in a Flow Shop with Multiple Processors. Industrial Engineering Research Conference Proceedings. Banff, Canada.


Refbacks

  • There are currently no refbacks.


Copyright (c) 2017 Industrial and Systems Engineering Review