A Hybrid Metaheuristic Algorithm for Robust Two-stage Flexible Flow Shop scheduling with Dedicated Assembly Lines under Uncertainty

Document Type : Research Paper

Author

Abstract

In this paper, the problem of scheduling and sequencing of multi-objective two-stage flexible flow shop with dedicated assembly lines, which produce various products during multiple planning periods, is proposed. The objectives of the proposed model are minimizing maximum completion time of products and total average weighted tardiness of production products. The first stage of the proposed flexible flow shop involves of several different parallel machines in site I and one machine in site II, and the second stage involves of two specific dedicated assembly lines. Each product has a specific bill of materials as well as has its own specific configuration which leading to difference processing times to assemble. Products composed of only single-process components are assigned to the first assembly line and products composed of at least a two-process component are assigned to the second assembly line. Components are placed on the associated dedicated assembly line in the second phase after completion of production process on the assigned machines in the first phase and final products will be produced by assembling the components. Uncertainty of demand of final products is handled via robust optimization technique based on the concept of uncertainty budget. The main contribution of this paper is development of a new mathematical model in flexible flow shop scheduling problem with dedicated assembly lines under uncertainty and presentation of a novel hybrid meta-heuristic for solving the proposed model. Due to the NP-hard nature of the proposed multi-objective problem, a hybrid evolutionary metaheuristic based on the strange Pareto evolutionary algorithm II is developed that incorporates a customized adaptive large neighborhood search as its local search heuristic. Extensive computational results illustrate the efficiency of the proposed model and solution algorithm in dealing with robust multi-objective flexible flow shop problem.

Keywords

References

[1] Sangsawang, C., Sethanan, K., Fujimoto, T., Gen, M.c. (2015). “Metaheuristic Optimization Approaches For Two-Stage Reentrant Flexible Flow Shop With Blocking Constraint”. Expert Systems with Applications, Vol 42(15): pp. 2395-2410.
[2] Linn, R., Zhang, W. (1999). “Hybrid Flow Shop Scheduling:  A Survey”. Comput.  Ind.  Eng., Vol 37: pp. 57–61.
[3] Gupta, J., Hariri, A., Potts, P. (1997). “Scheduling  A  Two-Stage  Hybrid  Flow  Shop  With  Parallel  Machines  at  The  First  Stage”. Ann.  Oper.  Res., Vol 69: pp. 171–191.
[4] Haouari, M., Hidri, L., Gharbi, A. (2006). “Optimal Scheduling of a Two-Stage Hybrid Flow Shop”. Math.  Methods Oper. Res., Vol 64: pp. 107–124.
[5] Hall, N.G., Sriskandarajah, C. (1996). “A  Survey  of  Machine  Scheduling  Problems  With  Blocking  and  No-Wait  In  Process”. Oper.  Res., Vol 44: pp. 510–525.
[6] Ruiz, R., S erifo˘ glu, F.S., Urlings, V. (2008). “Modeling Realistic Hybrid Flexible Flow shop Scheduling Problems”. Comput.  Oper.  Res., Vol 35: pp. 1151-1175.
[7] Allaoui, H., Artiba, A. (2006). “Scheduling Two-Stage Hybrid Flow Shop with Availability Constraints”. Comput.  Oper.  Res., Vol 33: pp. 1399–1419.
[8] Carpov, S., Carlier, J., Nace, D., Sirdey, R. (2012). “Two-Stage  Hybrid  Flow  Shop  With  Precedence  Constraints  and  Parallel  Machines  at  Second  Stage”. Comput.  Oper.  Res., Vol 39: pp. 736–745.
[9] Nikzad, F., Rezaeian, J., Mahdavi, I., Rastgar, I. (2015). “Scheduling of Multi-Component Products in a Two-Stage Flexible Flow Shop”. Applied Soft Computing, Vol 32: pp. 132–143.
[10] Lin, H.-T., Liao, C.J. (2003). “A  Case  Study  in  a  Two-Stage  Hybrid  Flow  Shop With  Setup  Time  and  Dedicated  Machines”. Int. J. Prod. Econ., Vol 86: pp. 133–143.
[11] Cheng, T.E., Lin, B.M., Tian, Y. (2009). “Scheduling  of  a  Two-Stage  Differentiation  Flow Shop To  Minimize  Weighted  Sum  of  Machine  Completion  Times’. Comput.  Oper.  Res., Vol 36: pp. 3031–3040.
[12] Brah, S.A., Hunsucker, J.L. (1991). “Branch  and  Bound  Algorithm  For  The  Flow  Shop  With Multiple  Processors”. Eur.  J.  Oper.  Res., Vol 51: pp. 88–99.
[13] Riane, F., Artiba, A., Elmaghraby, S.E. (2002). “Sequencing a Hybrid Two-Stage Flow Shop with Dedicated Machines”. Int.  J.  Prod.  Res., Vol 40: p. 4353–4380.
[14] Li, Z., Liu, J., Chen, Q., Mao, N., Wang, X. (2015). “Approximation Algorithms for the Three-Stage Flexible Flow Shop Problem with Mid Group Constraint”. Expert Systems with Applications, Vol 42(7): pp. 3571-3584.
[15] Jolai, F., Asefi, H., Rabiee, M., Ramezani, P. (2013). “Bi-Objective Simulated Annealing Approaches For No-Wait Two-Stage Flexible Flow Shop Scheduling Problem”. Scientia Iranica E, Vol 20(3): pp. 861–872.
[16] Gerstl, E., Mosheiov, G. (2014). “A Two-Stage Flexible Flow Shop Problem with Unit-Execution-Time Jobs and Batching”. Int. J. Production Economics, Vol 158: pp. 171–178.
[17] Wei, Q., E. Shan, Kang, L. (2014). “A FPTAS for a Two-Stage Hybrid Flow Shop Problem and Optimal Algorithms for Identical Jobs”. Theoretical Computer Science, Vol 524: pp. 78–89.
[18] Johnson, S.M. (1954). “Optimal Two and Three Stage Production Schedules With Setup Times Included”. Naval  Res.  Log., Quart.  1: pp. 61–68.
[19] Lee, C.-Y., Cheng, T., Lin, B.M. (1993). “Minimizing the Makespan in the 3-Machine Assembly Type Flow Shop Scheduling Problem”. Manage.  Sci., 39: pp. 616–625.
[20] Hariri, A., Potts, C. (1997). “A branch and bound algorithm for the two-stage assembly
scheduling problem”. Problem, Eur.  J.  Oper.  Res., 103: pp. 547–556.
[21] Fattahi, P., Hosseini, S.M.H., Jolai, F., Tavakkoli-Moghaddam, R., (2014). “A  Branch  and Bound  Algorithm  For  Hybrid  Flow  Shop  Scheduling  Problem  With  Setup  Time and  Assembly  Operations”. Appl.  Math.  Model., Vol 38: pp. 119-134.
[22] Yokoyama, M., (2004). “Scheduling  For  Two-Stage  Production  System  With  Setup  and Assembly  Operations”. Comput.  Oper.  Res., Vol 31: pp. 2063–2078.
[23] Yokoyama, M., Santos, D.L. (2005). “Three-Stage  Flow-Shop  Scheduling  With  Assembly Operations  To  Minimize  The  Weighted  Sum  of  Product  Completion  Times”. Eur.  J. Oper.  Res., Vol 161: pp. 754–770.
[24] Yokoyama, M. (2008). “Flow Shop Scheduling with Setup and Assembly Operations”. Eur. J.  Oper.  Res., Vol 187: pp. 1184–1195.
[25] Yan, H.-S., Wan, X.-Q., Xiong, F.-L. (2014). “A  Hybrid  Electromagnetism-Like  Algorithm For  Two-Stage  Assembly  Flow  Shop  Scheduling  Problem”. Int.  J.  Prod.  Res., Vol 52(14): pp. 1–14.
[26] Xiong, F., Xing, K., Wang, F. (2015). “Scheduling  A  Hybrid  Assembly-Differentiation Flows Shop  To  Minimize  Total  Flow  Time” . Eur.  J.  Oper.  Res., Vol 240: pp. 338–354.
[27] Shoaardebili, N., Fattahi, P. (2014). “Multi-Objective  Meta-Heuristics  To  Solve  Three-Stage Assembly  Flow  Shop  Scheduling  Problem  With  Machine  Availability  Constraints”. Int. J. Prod. Res., Vol 53(3): pp. 1-25.
[28] Besbes, W., Loukil, T., Teghem, J. (2010). “A  Two-Stage  Flow  Shop  with  Parallel  Dedicated Machines”, in Proceedings  of  the  Conference  Mosim.
[29] Wang, S., Liu, M. (2013). “A  Heuristic  Method  For  Two-Stage  Hybrid  Flow  Shop  with  Dedicated  Machines”. Comput.  Oper.  Res., Vol 40: pp. 438–450.
[30] Hadda, H., Dridi, N., Hajri-Gabouj, S. (2014). “Exact  Resolution  of  The  Two-Stage  Hybrid Flow Shop  With  Dedicated  Machines”. Optim.  Lett., Vol 8(8): pp. 1–11.
[31] Abbas, M., Bekrar, A., Benmansour, R., Hanafi, S. (2014). “On  The  Complexity  of  Robotic Flow  Shop  With  Transportation  Constraints”, in ROADEF-15ème  congrès  annuel de  la  Société  franc¸  aise  de  recherche  opérationnelle  et  d’aide  à  la  décision.
[32] Bertsimas, D., Sim, M. (2002). “The Price of Robustness”. Oper.  Res., Vol 52(1): pp. 35 - 53.
]33[ بهشتی‌نیا، م. قاضی وکیلی، ن. (1394). "ارزیابی الگوریتم‌های زمان‌بندی تولید کارگاهی انعطاف‌پذیر و مقایسه آن‌ها با الگوریتم ژنتیک دو بخشی". مجله مدل‌سازی در مهندسی، 40، 16-1.
[34] Altiparmak, F., Gen, M., Lin, L., Karaoglan, I. (2008). “A Steady-State Genetic Algorithm for Multi-Product Supply Chain Network Design”. Computers & Industrial Engineering, Vol 56: 521-537.
[35] Hasani, A., Zegordi, S.H., Nikbakhsh, E. (2015). “Robust Closed-Loop Global Supply Chain Network Design under Uncertainty: The Case of the Medical Device Industry”. International Journal of Production Research, Vol 53(5): pp. 1596-1624.
[36] Fahimnia, B., Farahani, R.Z., Sarkis, J., (2013) “Integrated Aggregate Supply Chain Planning Using Memetic Algorithm – A Performance Analysis Case Study”. International Journal of Production Research, Vol 15(18): pp. 5354-5373.
[37] Moscato, P., Norman, M.G., (1992). “A Memetic Approach for The Traveling Salesman Problem Implementation of A Computational Ecology For Combinatorial Optimization On Message-Passing Systems”. Parallel Computing and Transporter Applications, pp. 177–186.
[38] Fonseca, C.M., Fleming, P.J. (1993). “Genetic Algorithms for Multi-objective Optimization: Formulation, Discussion and Generalization”, in the Fifth International Conference on Genetic Algorithms, M. Kaufmann, Editor. SanMateo, California.
[39] Horn, J., Nafpliotis, N., Goldberg, D.E. (1994). “A Niched Pareto Genetic Algorithm for Multi-objective Optimization, in Proceedings of the First IEEE Conference on Evolutionary Computation”, IEEE World Congress on Computational Computation, N. Piscataway, Editor. IEEE Press.
[40] Srinivas, N., Deb, K. (1994). “Multi-objective Optimization Using Non-dominated Sorting in Genetic Algorithms”. Evolutionary Computation, Vol 2(3): pp. 221–248.
[41] Zitzler, E., Thiele, L. (1999). “Multi-objective Evolutionary Algorithms: A Comparative Case Study and the Strength Pareto Approach”. IEEE Transactions on Evolutionary Computation, Vol 3(4): pp. 257–271.
[42] Knowles, J.D., Corne, D.W. (1999). “The Pareto Archived Evolution Strategy: A New Baseline Algorithm for Pareto Multi-objective Optimization”, in Congress on Evolutionary Computation (CEC99), N. Piscataway, Editor. IEEE Press. pp. 98–105.
[43] Deb, K., Agrawal, S., Pratap, A., Meyarivan, T. (2000). “A fast elitist non-dominated sorting genetic algorithm for multi-objective optimization: NSGA-II, in Parallel Problem Solving from Nature”. Springer: Berlin. pp. 849–858.
[44] Corne, D.W., Knowles, J.D., Oates, M.J. (2000). “The Pareto Envelope-Based Selection Algorithm for Multi-objective Optimization”, in Parallel Problem Solving from Nature. Springer: Berlin. pp. 839–848.
[45] Zitzler, E., Laumanns, M., Thiele, L. (2001). “SPEA2: Improving the Strength Pareto Evolutionary Algorithm”. Department of Electrical Engineering: Swiss Federal Institute of Technology (ETH) Zurich.
[46] Baños, R., Ortega, J., Gilb, C., Márquez, A.L., Toro, F.D. (2013). “A Hybrid Meta-Heuristic for Multi-Objective Vehicle Routing Problems with Time Windows”. Computers & Industrial Engineering, Vol 65: pp. 286–296.
[47] Ropke, S., Pisinger, D. (2006). “An Adaptive Large Neighborhood Search Heuristic for the Pickup and Delivery Problem with Time Windows”. TRANSPORTATION SCIENCE, Vol 40: pp. 455-472.
[48] Talbi, E.G. (2009). “Metaheuristics: From Design to Implementation”. Wiley.
[49] Eskandarpour, M., Nikbakhsh, E., Zegordi, S.H. (2014). “Variable Neighborhood Search for the Bi-Objective Post-Sales Network Design Problem: A Fitness Landscape Analysis Approach”. Computers & Operations Research, Vol 52: pp. 300–314.
[50] Hasani, A., Zegordi, S.H., Nikbakhsh, E. (2015).  “Robust Closed-Loop Global Supply Chain Network Design under Uncertainty: The Case of the Medical Device Industry”. International Journal of Production Research, Vol 53(5): pp. 1596-1624.
[51] Altiparmak, F., Gen, M., Lin, L., Paksoy, T. (2006). “A Genetic Algorithm Approach For Multi-Objective Optimization of Supply Chain Networks”. Computers & Industrial Engineering, Vol 51: pp. 196-215.
[52] Eskandarpour, M., E. Nikbakhsh, Zegordi, S.H. (2014). “Variable Neighborhood Search for the Bi-Objective Post-Sales Network Design Problem: A Fitness Landscape Analysis Approach”. Computers & Operations Research, Vol 52(B): pp. 300–314.
 
Journal of Modeling in Engineering
Volume 15, Issue 50
June 2017
Pages 25-47

Files

History

  • Receive Date: 16 September 2015
  • Revise Date: 15 January 2016
  • Accept Date: 10 February 2016

Share

How to cite

Statistics