A novel bi-objective model for a job shop scheduling problem with consideration of Fuzzy parameters, modified learning effects and multiple preventive maintenance activities

Document Type : Article

Authors

1 Department of Industrial Engineering, University of Kurdistan, Pasdaran Boulevard, Sanandaj, Iran

2 Department of Industrial Engineering, Faculty of Engineering, University of Kurdistan, Sanandaj, Iran

Abstract

This paper aims at introducing a novel bi-objective model for a Job Shop Scheduling Problem (JSSP) in order to minimize makespan and maximum tardiness simultaneously. Some realistic assumptions, i.e. Fuzzy processing times and due dates involving triangular possibility distributions, transportation times, availability constraints, modified position-based learning effects on processing times, and sum-of-processing-time based learning effects on duration of maintenance activities have been considered, to provide a more general and practical model for the JSSP. Based on the learning effects, Processing times decrease as a machine performs an operation frequently, and workers gain working skills and experiences. In this paper based on DeJong’s learning effect a novel and modified formulation has been proposed for this effect. According to the above-mentioned assumptions, a novel mixed-integer linear programming (MILP) model for the JSSP is suggested. The proposed model is first converted to an auxiliary crisp model, given that model is a possibilistic programming, it is then solved by the TH and ε-constraint methods for small instances, and the results are compared. For medium and large instances, five metaheuristic algorithms, including NSGA-ΙΙΙ, PESA-ΙΙ, SPEA-ΙΙ, NSGA-ΙΙ, and MOEA/D are utilized, and the results are finally compared on the basis of three performance metrics.

Keywords

References

References:
1. Torabi, S.A. and Hassini, E. "An interactive possibilistic programming approach for multiple objective supply chain master planning", Fuzzy Sets and Systems, 159(2), pp. 193-214 (2008).
2. Muth, J.F. and Thompson, G.L., Industrial Scheduling, Englewood Cliffs, New Jersey (1963).
3. Biskup, D. "Single-machine scheduling with learning considerations", European Journal of Operational Research, 115(1), pp. 173-178 (1999).
4. Biskup, D. "A state-of-the-art review on scheduling with learning effect", European Journal of Operational Research, 188(2), pp. 188-315 (2008).
5. Azzouz, A., Ennigrou, M., and Ben Said, L. "Scheduling problems under learning effects: classification and cartography", International Journal of Production Research, 56(4), pp. 1642-1661 (2018).
6. Mousavipour, S.H., Farughi, H., and Ahmadizar, F. "A job shop scheduling problem with sequence-dependent setup times considering position-based learning effects and availability constraints", International Journal of Industrial Engineering & Production Research, 30(3), pp. 329-340 (2019).
7. Mousavipour, S.H., Farughi, H., and Ahmadizar, F. "Job shop scheduling problem based on learning effects,  flexible maintenance activities and transportation times", Journal of Industrial and Systems Engineering, 12(3), pp. 107-119 (2019).
8. Tayebi Araghi, M.E., Jolai, F., and Rabiee, M. "Incorporating learning effect and deterioration for solving a SDST flexible job-shop scheduling problem with a hybrid meta-heuristic approach", International Journal of Computer Integrated Manufacturing, 27(8), pp. 733-746 (2014).
9. Renna, P. "Flexible job-shop scheduling with learning and forgetting effect by Multi-Agent System", International Journal of Industrial Engineering Computations, 10, pp. 521-534 (2019).
10. Okolowski, D. and Gawiejnowicz, S. "Exact and heuristic algorithms for Parallel-machine scheduling with DeJong's learning effect", Computers & Industrial Engineering, 59(2), pp. 272-279 (2010).
11. Lai, P.J. and Wu, H.C. "Using heuristic algorithms to solve the scheduling problems with job-dependent and machine-dependent learning effects", J Intell Manuf, 26, pp. 691-701 (2015).
12. Vahedi-Nouri, B., Fattahi, P., Tavakkoli-Moghaddam, R., et al. "A general flow shop scheduling problem with consideration of position-based learning effect and multiple availability constraints", International Journal of Advanced Manufacturing Technology, 73(5), pp. 601-611 (2014).
13. Amirian, H. and Sahraeian, R. "Augmented "ε constraint method in multi-objective flow shop problem with past sequence set-up times and a modified learning effect", International Journal of Production Research, 53(19), pp. 1-15 (2015).
14. Behnamian, J. and Zandieh, M. "Earliness and tardiness minimizing on a realistic hybrid flowshop scheduling with learning effect by advanced metaheuristic", Arab J Sci Eng, 38, pp. 1229-1242 (2013).
15. Gao, F., Liu, M., Wang, J.J., et al. "No-wait twomachine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times", International Journal of Production Research, 56(6), pp. 2361-2369 (2018).
16. Mousavi, S.M., Mahdavi, L., Rezaeian, J., et al.  Biobjective scheduling for the re-entrant hybrid  flow shop with learning effect and setup times", Scientia Iranica E, 25(4), pp. 2233-2253 (2018).
17. Schmidt, G. "Scheduling with limited machine availability", European Journal of Operational Research, 121(1), pp. 1-15 (2000).
18. Ma, Y., Chu, C., and Zuo, C. "A survey of scheduling with deterministic machine availability constraints", Computers & Industrial Engineering, 58(2), pp. 199- 211 (2010).
19. Hsu, C.J., Low, C., and Su, C.T. "A single-machine scheduling problem with maintenance activities to minimize Make Span", Applied Mathematics and Computation, 215(11), pp. 29-35 (2010).
20. Xu, D., Xu, Z., He, J., et al. "Mixed integer programming formulations for two-machine flow shop scheduling with an availability constraint", Arab J Sci Eng, 43, pp. 777-788 (2018).
21. Aggoune, R. "Two-job shop scheduling problems with availability constraints", 14th International Conference on Automated Planning and Scheduling, pp. 253-259 (2004).
22. Benttaleb, M., Hnaien, F., and Yalaoui, F. "Twomachine job shop problem under availability constraints on one machine: Makespan minimization", Computers & Industrial Engineering, 117, pp. 138- 151 (2018).
23. Tamssaouet, K., Dauzere-Peres, S., and Yugma, C. "Metaheuristics for the job-shop scheduling problem with machine availability constraints", Computers & Industrial Engineering, 125, pp. 1-8 (2018).
24. Naderi, B., Zandieh, M., and Fatemi Ghomi, S.M.T. "Scheduling sequence-dependent setup time job shops with preventive maintenance", Int J Adv Manuf Technol, 43(1), pp. 170-181 (2009).
25. Taraki, H., Tang, K., and Teyarachakul, S. "Learning effects on maintenance outsourcing", European Journal of Operational Research, 192(1), pp. 138-150 (2009).
26. Ahmadizar, F. and Shahmaleki, P. "Group-shop scheduling with sequence-dependent set-up and transportation times", Applied Mathematical Modelling, 38(21), pp. 5080-5091 (2014).
27. Hurink, J. and Knust, S. "Tabu search algorithms for job-shop problems with a single transport robot", European Journal of Operational Research, 162(1), pp. 99-111 (2005).
28. Nouri, H.E., Driss, O.B., and Ghedira, K. "Hybrid metaheuristics for scheduling of machines and transport robots in job shop environment", Appl. Intell, 45(3), pp. 808-828 (2016).
29. Sakawa, M. and Kubota, R. "Two-objective fuzzy job shop scheduling through genetic algorithm", Electronics and Communication in Japan (Part III: Fundamental Electronic Science), 84(4), pp. 60-68 (2001).
30. Lei, D. "Co-evolutionary genetic algorithm for fuzzy  flexible job shop scheduling", Applied Soft Computing, 12(8), pp. 2237-2245 (2012).
31. Ahmadizar, F. and Zarei, A. "Minimizing Make Span in a group shop with fuzzy release dates and processing times", Int J Adv Manuf Technol, 66(9-12), pp. 206- 219 (2013).
32. Noori-Darvisha, S., Mahdavi, I., and Mahdavi-Amir, N. "A bi-objective possibilistic programming model for open shop scheduling problems with sequencedependent setup times, fuzzy processing times, and fuzzy due dates", Applied Soft Computing, 12(4), pp. 1399-1416 (2012).
33. Wagner, H.M. "An integer linear-programming model for machine scheduling", Naval Rest Logis Q, 6(2), pp. 131-140 (1959).
34. Yang, D.L. and Kuo, W.H. "Single-machine scheduling with an actual time-dependent learning effect", Journal of the Operational Research Society, 58(10), pp. 1348-1353 (2007).
35. Lai, Y.J. and Hwang, C.L. "A new approach to some possibilistic linear programming problems", Fuzzy Sets and Systems, 49(2), pp. 121-133 (1992).
36. Deb, K., Pratap, A., Agarwal, S., et al. "A fast and elitist multi-objective genetic algorithm: NSGAII", IEEE Transactions on Evolutionary Computation, 6(2), pp. 182-97 (2002).
37. Zitzler, E., Laumanns, M., and Thiele, L. "SPEA2: Improving the strength Pareto evolutionary algorithm", Computer Engineering and Networks Laboratory (TIK), Department of Electrical Engineering Swiss Federal Institute of Technology (ETH), Zurich (2001).
38. Corne, D.W., Jerram, N.R., Knowles, J.D., et al. "PESA-II: Region-based selection in evolutionary multi-objective optimization", Proceedings of the Genetic and Evolutionary Computation Conference, pp. 283-290 (2001).
39. Gadhvia, B., Savsania, B., and Vivek, P. "Multiobjective optimization of vehicle passive suspension system using NSGA-II, SPEA2 and PESA-II", Procedia Technology, 23, pp. 361-368 (2016).
40. Deb, K. and Jain, H. "An evolutionary many-objective optimization algorithm using reference-point-based non-dominated sorting approach, part I: Solving problems with box constraints", IEEE International Transactions in Operational Research, 18(4), pp. 577-601 (2014).
41. Zhang, Q. and Li, H. "MOEA/D: A multi-objective evolutionary algorithm based on decomposition", IEEE Transaction on Evolutionary Computation, 11(6), pp. 712-731 (2007).
42. Poursabzi, O., Mohammadi, M., and Naderi, B. "An improved model and heuristic for capacitated lot-sizing and scheduling in job shop problems", Scientia Iranica E, 25(6), pp. 3667-3684 (2018).
43. Srinivas, N. and Deb, K. "Multi-objective optimization using non-dominated sorting in genetic algorithms", Evolutionary Computation, 2(3), pp. 221-248 (1994).
44. Schaffer, J.D. "Multiple objective optimizations with vector evaluated genetic algorithms and their applications", Proceedings of the First International Conference on Genetic Algorithms, Lawrence Erlbaum, Hillsdale, USA, pp. 93-100 (1985).
Scientia Iranica
Volume 29, Issue 6 - Serial Number 6
Transactions on Industrial Engineering (E)
November and December 2022
Pages 3418-3433

Files

History

  • Receive Date: 12 October 2019
  • Revise Date: 06 October 2020
  • Accept Date: 18 January 2021

Share

How to cite

Statistics