全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...
Engineering  2014 

A Branch-and-Bound Based Heuristic Algorithm for Minimizing Makespan in Machining-Assembly Flowshop Scheduling

DOI: 10.4236/eng.2014.613081, PP. 877-885

Keywords: Scheduling, Heuristic, Branch and Bound Algorithm, Machining-Assembly Flowshop, Makespan

Full-Text   Cite this paper   Add to My Lib

Abstract:

This paper proposes a heuristic algorithm, called list-based squeezing branch and bound algorithm, for solving a machine-fixed, machining-assembly flowshop scheduling problem to minimize makespan. The machine-fixed, machining-assembly flowshop consists of some parallel two-machine flow lines at a machining stage and one robot at an assembly stage. Since an optimal schedule for this problem is not always a permutation schedule, the proposed algorithm first finds a promising permutation schedule, and then searches better non-permutation schedules near the promising permutation schedule in an enumerative manner by elaborating a branching procedure in a branch and bound algorithm. The results of numerical experiments show that the proposed algorithm can efficiently provide an optimal or a near-optimal schedule with high accuracy such as mean relative error being less than 0.2% and the maximum relative error being at most 3%.

References

[1]  Sun, X., Morizawa, K. and Nagasawa, H. (2003) Powerful Heuristics to Minimize Makespan in Fixed, 3-Machine, Assembly-Type Flowshop Scheduling. European Journal of Operational Research, 146, 498-516.
http://dx.doi.org/10.1016/S0377-2217(02)00245-X
[2]  Johnson, S.M. (1956) An Optimal Two- and Three-Stage Production Scheduling with Setup Time Included. Naval Research Logistics Quarterly, 1, 61-68.
http://dx.doi.org/10.1002/nav.3800010110
[3]  Lee, C.-Y., Cheng, T.C.E. and Lin, B.M.T. (1993) Minimizing the Makespan in the 3-Machine Assembly-Type Flowshop Scheduling Problem. Management Science, 39, 616-625.
http://dx.doi.org/10.1287/mnsc.39.5.616
[4]  Potts, C.N., Sevast’janov, S.V., Strysevich, V.A., Van Wassenhove, L.N. and Zwaneveld, C.M. (1995) The Two-Stage Assembly Scheduling Problem: Complexity and Approximation. Operations Research, 43, 346-355.
http://dx.doi.org/10.1287/opre.43.2.346
[5]  Miyake, Y., Morizawa, K. and Nagasawa, H. (2002) A Branch-and-Bound Algorithm for Minimizing Makespan in a Machine-Fixed, Machining-Assembly Flowshop with Parallel Flowshop Lines. Journal of Japan Industrial Management Association, 53, 292-301.
[6]  Nagasawa, H. and Morizawa, K. (2002) Heuristic Scheduling in Machining-Assembly Flowshop with Parallel Two-Machine Flow Lines at Machining Stage. Journal of Japan Industrial Management Association, 53, 37-46.
[7]  Morizawa, K., Sun, X. and Nagasawa, H. (1998) Squeezing Branch and Bound Algorithm and Its Application to an N/M/F/F Max Problem. Proceedings of 1998 Japan USA Symposium on Flexible Automation, Otsu, 12-15 July 1998, 913-916.
[8]  Morizawa, K., Sun, X. and Nagasawa, H. (2003) Squeezing Branch and Bound Algorithm for the Machine-Fixed, Machining-Assembly Flowshop Scheduling Problem. International Journal of Manufacturing Technology and Management, 5, 20-27.
http://dx.doi.org/10.1504/IJMTM.2003.002526
[9]  Dannenbring, G.D. (1977) An Evaluation of Flowshop Sequencing Heuristics. Management Science, 23, 1174-1182.
http://dx.doi.org/10.1287/mnsc.23.11.1174

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133