A Heuristic Based On Makespan Lower Bounds in Flow Shops with Multiple Processors
Main Article Content
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.
Article Sidebar
Published
August 4, 2017
Article Details
Section
Articles
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
The copyediting stage is intended to improve the flow, clarity, grammar, wording, and formatting of the article. It represents the last chance for the author to make any substantial changes to the text because the next stage is restricted to typos and formatting corrections. The file to be copyedited is in Word or .rtf format and therefore can easily be edited as a word processing document. The set of instructions displayed here proposes two approaches to copyediting. One is based on Microsoft Word's Track Changes feature and requires that the copy editor, editor, and author have access to this program. A second system, which is software independent, has been borrowed, with permission, from the Harvard Educational Review. The journal editor is in a position to modify these instructions, so suggestions can be made to improve the process for this journal.
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.
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.
How to Cite
A Heuristic Based On Makespan Lower Bounds in Flow Shops with Multiple Processors. (2017). Industrial and Systems Engineering Review, 5(1), 33-43. https://doi.org/10.37266/ISER.2017v5i1.pp33-43
How to Cite
A Heuristic Based On Makespan Lower Bounds in Flow Shops with Multiple Processors. (2017). Industrial and Systems Engineering Review, 5(1), 33-43. https://doi.org/10.37266/ISER.2017v5i1.pp33-43
