The Effect of Worker Learning on Scheduling Jobs in a Hybrid Flow Shop: A Bi-Objective Approach

Abstract

This paper studies learning effect as a resource utilization technique that can model improvement in worker’s ability as a result of repeating similar tasks. By considering learning of workers while performing setup times, a schedule can be determined to place jobs that share similar tools and fixtures next to each other. The purpose of this paper is to schedule a set of jobs in a hybrid flow shop (HFS) environment with learning effect while minimizing two objectives that are in conflict: namely maximum completion time (makespan) and total tardiness. Minimizing makespan is desirable from an internal efficiency viewpoint, but may result in individual jobs being scheduled past their due date, causing customer dissatisfaction and penalty costs. A bi-objective mixed integer programming model is developed, and the complexity of the developed bi-objective model is compared against the bi-criteria one through numerical examples. The effect of worker learning on the structure of assigned jobs to machines and their sequences is analyzed. Two solution methods based on the hybrid water flow like algorithm and non-dominated sorting and ranking concepts are proposed to solve the problem. The quality of the approximated sets of Pareto solutions is evaluated using several performance criteria. The results show that the proposed algorithms with learning effect perform well in reducing setup times and eliminate the need for setups itself through proper scheduling.

Keywords

Bi-objective scheduling / hybrid flow shop / learning effect / meta-heuristic

References

[1] Agnetis A., Billaut J.-C., Gawiejnowicz S., Pacciarelli D., Soukhal A.. Multiagent scheduling, 2014, 10(1007): 978-3.

[2] Behjat S., Salmasi N.. Total completion time minimisation of no-wait flowshop group scheduling problem with sequence dependent setup times. European Journal of Industrial Engineering, 2017, 11(1): 22-48.

[3] Behnamian J., Zandieh M.. Earliness and tardiness minimizing on a realistic hybrid flowshop scheduling with learning effect by advanced metaheuristic. Arabian Journal for Science and Engineering, 2013, 38(5): 1-14.

[4] Biskup D.. Single machine scheduling with learning considerations. European Journal of Operational Research, 1999, 115(1): 173-178.

[5] Biskup D.. A state-of-the-art review on scheduling with learning effect. European Journal of Operational Research, 2008, 188: 315-329.

[6] Cheng T.C.E., Kuo W.H., Yang D.L.. Scheduling with a position-weighted learning effect. Optimization Letters, 2014, 8(1): 293-306.

[7] Cheng T.C.E., Wang G.. Single machine scheduling with learning effect considerations. Annals of Operations Research, 2000, 98(1-4): 273-290.

[8] Choong F. P.-A. S., Alias M.Y.. Meta-heuristic methods in hybrid flow shop scheduling problem. Expert Systems with Applications, 2011, 38(9): 10787-10793.

[9] Coello C.A.C., Lamont G.B., Van Veldhuizen D.A.. Evolutionary Algorithms for Solving Multi-Objective Problems, 2007.

[10] Deb K., Pratap A., Agarwal S., Meyarivan T.. A fast and elitist multi-objective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 2002, 6(2): 182-197.

[11] Eren T., Güner E.. A bi-criteria flow shop scheduling with a learning effect. Applied Mathematical Modelling, 2008, 32: 1719-1733.

[12] Eren T., Güner E.. A bicriteria parallel machine scheduling with a learning effect. International Journal of Advanced Manufacturing Technology, 2009, 40: 1202-1205.

[13] Govindan K., Balasundaram R., Baskar N., Asokan P.. A hybrid approach for minimizing makespan in permutation flowshop scheduling. Journal of Systems Science and Systems Engineering, 2016, 26(1): 1-27.

[14] Gupta J.. Two-stage hybrid flow shop scheduling problem. Journal of Operational Research Society, 1988, 39(4): 359-364.

[15] Jadaan O., Rajamani L., Rao C.. Non-dominated ranked genetic algorithm for solving multi-objective optimization problems: NRGA. Journal of Theoretical and Applied Information Technology, 2008, 4(1): 61-68.

[16] Jones D.F., Mirrazavi S.K., Tamiz M.. Multi-objective meta-heuristics: an overview of the current state of the art. European Journal of Operation Research, 2002, 137(1): 1-9.

[17] Karimi N., Davoudpour H.. Multi-objective colonial competitive algorithm for hybrid flowshop problem. Applied Soft Computing, 2016, 49: 725-733.

[18] Kuo W.-H., Yang D.-L.. Minimizing the total completion time in a single-machine scheduling problem with a time-dependent learning effect. European Journal of Operational Research, 2006, 174: 1184-1190.

[19] Kurz M.E., Askin R.G.. Comparing scheduling rules for flexible flow lines. International Journal of Production Economics, 2003, 85(3): 371-388.

[20] Kurz M.E., Askin R.G.. Scheduling flexible flow lines with sequence dependent setup times. European Journal of Operational Research, 2004, 159(1): 66-82.

[21] Mousavi S.M., Mahdavi I., Rezaeian J., Zandieh M.. An efficient bi-objective algorithm to solve re-entrant hybrid flow shop scheduling with learning effect and setup times. Operational Research, 2016, 16: 1-36.

[22] Mousavi S.M., Zandieh M.. An efficient hybrid algorithm for a bi-objectives hybrid flow shop scheduling. Intelligent Automation & Soft Computing, 2016, 22: 1-8.

[23] Murata T., Ishibuchi H., Tanaka H.. Multi-objective genetic algorithm and its application to flowshop scheduling. Computer and Industrial Engineering, 1996, 30(4): 957-968.

[24] Naderi B., Zandieh M., Roshanaei V.. Scheduling hybrid flow shops with sequence dependent setup times to minimize makespan and maximum tardiness. International Journal of Advanced Manufacturing Technology, 2009, 41(11-12): 1186-1198.

[25] Pargar F., Zandieh M.. A bi-criteria SDST hybrid flow shop scheduling with learning effect of setup times: Water flow-like algorithm approach. International Journal of Production Research, 2012, 50(10): 2609-2623.

[26] Pinedo M.. Scheduling Theory Algorithms and Systems, 2015, Berlin: Springer.

[27] Quadt D., Kuhn H.. A taxonomy of flexible flow line scheduling procedures. European Journal of Operational Research, 2007, 178(3): 686-698.

[28] Ribas I. R. L., & J.M. Fr.amiñan. Review and classification of hybrid flow shop scheduling problems from a production system and a solution procedure perspective. Computers and Operational Research, 2010, 37(8): 1439-1454.

[29] Ruiz R., Rodriguez J.A.. The hybrid flow shop scheduling problem. European Journal of Operational Research, 2010, 205(1): 1-18.

[30] Schaffer J.D.. Multiple objective optimization with vector evaluated genetic algorithms. Proceedings of First International Conference on Genetic Algorithms and Their Applications, 1985, Pittsburgh, PA, USA: Carnegie-Mellon University 93-100.

[31] Soroush H.M.. Scheduling with job-dependent past-sequence-dependent setup times and job-dependent position-based learning effects on a single processor. European Journal of Industrial Engineering, 2015, 9(3): 277-307.

[32] Tavakkoli-Moghaddam R., Rahimi-Vahed A.R., Mirzaei A.H.. Solving a multi-objective no-wait flow shop scheduling problem with an immune algorithm. The International Journal of Advanced Manufacturing Technology, 2008, 36(9-10): 969-981.

[33] Wang L.Y., Wang J.J., Wang J.B., Feng E.M.. Scheduling jobs with general learning functions. Journal of Systems Science and Systems Engineering, 2011, 20(1): 119-125.

[34] Wu Y.B., Wang J.J.. Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times. Neural Computing and Applications, 2016, 27(4): 937-943.

[35] Yenisey M.M., Yagmahan B.. Multi-objective permutation flow shop scheduling problem: literature review, classification and current trends. Omega, 2014, 45: 119-135.

[36] Yue Q., Wan G.. Order scheduling with controllable processing times, common due date and the processing deadline. Journal of Systems Science and Systems Engineering, 2017, 26(2): 199-218.

[37] Zandieh M., Ghomi S.F., Husseini S.M.. An immune algorithm approach to hybrid flow shops scheduling with sequence-dependent setup times. Applied Mathematics and Computation, 2006, 180(1): 111-127.

[38] Zhou A., Qu B.Y., Li H., Zhao S.Z., Suganthan P.N., Zhang Q.. Multiobjective evolutionary algorithms: A survey of the state of the art. Swarm and Evolutionary Computation, 2011, 1(1): 32-49.