Genetic algorithm based on greedy strategy in unrelated parallel-machine scheduling problem using fuzzy approach with periodic maintenance and process constraints

Document Type : Research Paper

Authors

Department of industrial engineering, faculty of engineering, Kharazmi University, Tehran, Iran

Abstract

Nowadays, in production environments where the production system is parallel machines, the reliability of the machines is important and the uncertainty of scheduling parameters is common. In this paper, unrelated parallel machine scheduling problem using a fuzzy approach with machines maintenance activities and process constraints is of concern. An important application of this problem is in the production of products that the due dates are defined as a time window and the best due date is close to the middle of the time window and the jobs processing times depend on other factors such as operator and their value is not specified and are announced as interval under uncertainty. In this study, first, a fuzzy mathematical model is proposed in which changing between a fuzzy approach and a deterministic model is described. Then, since the problem is NP-hard, a fuzzy-based genetic algorithm to solve large instances is developed. In this algorithm, a greedy decoding approach according to fuzzy parameters is developed. Numerical experiments are used to evaluate the performance of the developed algorithm. It is concluded that the proposed algorithm shows great performance in large instances and is superior to the proposed mathematical model in small instances too.

Keywords

References

  1. Sun and H. Li, (2010). Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines. Int. J. Prod. Econ, vol. 124, no. 1, pp. 151–158.
  2. Zhao, M. Ji, and H. Tang, (2011). Parallel-machine scheduling with an availability constraint. Comput. Ind. Eng, vol. 61, no. 3, pp. 778–781.
  3. Tan, Y. Chen, and A. Zhang, (2013). On the exact bounds of SPT for scheduling on parallel machines with availability constraints. Int. J. Prod. Econ, vol. 146, no. 1, pp. 293–299.
  4. Xu and D.-L. Yang, (2013). Makespan minimization for two parallel machines scheduling with a periodic availability constraint: mathematical programming model, average-case analysis, and anomalies. Appl. Math. Model, vol. 37, no. 14, pp. 7561–7567.
  5. Wang and T. C. E. Cheng, (2015). A heuristic for scheduling jobs on two identical parallel machines with a machine availability constraint, Int. J. Prod. Econ, vol. 161, pp. 74–82.

J.-Y. Lee and Y.-D. Kim, (2015). A branch and bound algorithm to minimize total tardiness of jobs in a two identical-parallel-machine scheduling problem with a machine availability constraint. J. Oper. Res. Soc, vol. 66, no. 9, pp. 1542–1554.

  1. He, Q. Li, and D. Xu, (2016). Scheduling two parallel machines with machine-dependent availabilities. Comput. Oper. Res, vol. 72, pp. 31–42.
  2. Shen, D. Wang, and X.-Y. Wang, (2013). Parallel-machine scheduling with non-simultaneous machine available time. Appl. Math. Model, vol. 37, no. 7, pp. 5227–5232.
  3. Huo and H. Zhao, (2015). Total completion time minimization on multiple machines subject to machine availability and makespan constraints. Eur. J. Oper. Res, vol. 243, no. 2, pp. 547–554.

W.-C. Lee, J.-Y. Wang, and L.-Y. Lee, (2015). A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity. J. Oper. Res. Soc, vol. 66, no. 11, pp. 1906–1918.

  1. Yin, Y. Wang, T. C. E. Cheng, (2017). W. Liu, and J. Li, Parallel-machine scheduling of deteriorating jobs with potential machine disruptions. Omega, vol. 69, pp. 17–28.
  2. Suresh and D. GHAUDHURI, (1996). Scheduling of unrelated parallel machines when machine availability is specified. Prod. Plan. Control, vol. 7, no. 4, pp. 393–400.
  3. Jiang and J. Tan, (2016). Scheduling with job rejection and no simultaneous machine available time on unrelated parallel machines. Theor. Comput. Sci, vol. 616, pp. 94–99.

 

  1. Ahmadizar, K. Mahdavi, and J. Arkat, (2019). Unrelated parallel machine scheduling with processing constraints and sequence dependent setup times. Adv. Ind. Eng, vol. 53, no. 1, pp. 495–507.
  2. Avalos-Rosales, F. Angel-Bello, A. Álvarez, and Y. Cardona-Valdés, (2018). Including preventive maintenance activities in an unrelated parallel machine environment with dependent setup times. Comput. Ind. Eng, vol. 123, pp. 364–377.
  3. Lu, X. Liu, J. Pei, M. T. Thai, and P. M. Pardalos, (2018). A hybrid ABC-TS algorithm for the unrelated parallel-batching machines scheduling problem with deteriorating jobs and maintenance activity. Appl. Soft Comput, vol. 66, pp. 168–182.
  4. Balin, (2011). Parallel machine scheduling with fuzzy processing times using a robust genetic algorithm and simulation. Inf. Sci, vol. 181, no. 17, pp. 3551–3569.
  5. C. Chyu and W. S. Chang, (2011). Optimizing fuzzy makespan and tardiness for unrelated parallel machine scheduling with archived metaheuristics. Int. J. Adv. Manuf. Technol, vol. 57, no. 5–8, pp. 763–776.
  6. M. Senthilkumar, V. Selladural, K. Raja, and V. Thirunavukkarasu, (2011). A hybrid algorithm based on pso and aco approach for solving combinatorial fuzzy unrelated parallel machine scheduling problem.
  7. Alcan and H. Balişgil, (2012). A genetic algorithm application using fuzzy processing times in non-identical parallel machine scheduling problem. Adv. Eng. Softw, vol. 45, no. 1, pp. 272–280.
  8. A. Torabi, N. Sahebjamnia, S. A. Mansouri, and M. A. Bajestani, (2013). A particle swarm optimization for a fuzzy multi-objective unrelated parallel machines scheduling problem. Appl. Soft Comput, vol. 13, no. 12, pp. 4750–4762.
  9. Behnamian, (2014). Particle swarm optimization-based algorithm for fuzzy parallel machine scheduling. Int. J. Adv. Manuf. Technol, vol. 75, no. 5–8, pp. 883–895.
  10. C. Yeh, P. J. Lai, W. C. Lee, and M. C. Chuang, (2014). Parallel-machine scheduling to minimize makespan with fuzzy processing times and learning effects. Inf. Sci., vol. 269, pp. 142–158.
  11. Naderi-Beni, E. Ghobadian, S. Ebrahimnejad, and R. Tavakkoli-Moghaddam, (2014). Fuzzy bi-objective formulation for a parallel machine scheduling problem with machine eligibility restrictions and sequence-dependent setup times. Int. J. Prod. Res, vol. 52, no. 19, pp. 5799–5822.
  12. Rostami, A. E. Pilerood, and M. M. Mazdeh, (2015). Multi-objective parallel machine scheduling problem with job deterioration and learning effect under fuzzy environment. Comput. Ind. Eng, vol. 85, pp. 206–215.
  13. K. Nailwal, D. Gupta, and S. Sharma, (2015). Fuzzy bi-criteria scheduling on parallel machines involving weighted flow time and maximum tardiness. Cogent Math, vol. 2, no. 1, p. 1019792.
  14. W. Liao and P. Su, (2017). Parallel machine scheduling in fuzzy environment with hybrid ant colony optimization including a comparison of fuzzy number ranking methods in consideration of spread of fuzziness. Appl. Soft Comput. J., vol. 56, pp. 65–81.
  15. Li, J. Chen, H. Fu, Z. Jia, and W. Fu, (2019). Uniform parallel machine scheduling with fuzzy processing times under resource consumption constraint. Appl. Soft Comput, p. 105585.
  16. Jia, J. Yan, J. Y. T. Leung, K. Li, and H. Chen, (2019). Ant colony optimization algorithm for scheduling jobs with fuzzy processing time on parallel batch machines with different capacities. Appl. Soft Comput, vol. 75, pp. 548–561.
  17. Rezaeian, S. Mohammad-Hosseini, S. Zabihzadeh, and K. Shokoufi, (2020).Fuzzy Scheduling Problem on Unrelated Parallel Machine in JIT Production System. Artif. Intell. Evol., pp. 17–33.
  18. Liu, F. Chu, F. Zheng, C. Chu, and M. Liu, (2020). Parallel machine scheduling with stochastic release times and processing times. Int. J. Prod. Res., pp. 1–20.
  19. Li, J. Chen, H. Fu, Z. Jia, and J. Wu, (2020). Parallel machine scheduling with position-based deterioration and learning effects in an uncertain manufacturing system. Comput. Ind. Eng., vol. 149, p. 106858.
  20. A. Arık, M. Schutten, and E. Topan, (2021). Weighted Earliness/Tardiness Parallel Machine Scheduling Problem with a Common Due Date. Expert Syst. Appl., p. 115916.
  21. Khalifa, (2020). On single machine scheduling problem with distinct due dates under fuzzy environment. Int. J. Supply Oper. Manag, vol. 7, no. 3, pp. 272–278.
  22. Midya, S. Kumar Roy, and G. Wilhelm Weber, (2021). Fuzzy multiple objective fractional optimization in rough approximation and its aptness to the fixed-charge transportation problem. RAIRO--Operations Res, vol. 55, no. 3.
  23. Midya, S. K. Roy, and F. Y. Vincent, (2021). Intuitionistic fuzzy multi-stage multi-objective fixed-charge solid transportation problem in a green supply chain. Int. J. Mach. Learn. Cybern, vol. 12, no. 3, pp. 699–717.
  24. K. Roy and S. Midya, (2019). Multi-objective fixed-charge solid transportation problem with product blending under intuitionistic fuzzy environment. Appl. Intell, vol. 49, no. 10, pp. 3524–3538.

A.Mondal, S. K. Roy, and S. Midya, (2021). Intuitionistic fuzzy sustainable multi-objective multi-item multi-choice step fixed-charge solid transportation problem. J. Ambient Intell. Humaniz. Comput, pp. 1–25.

  1. K. Roy, S. Midya, and G.-W. Weber, (2019). Multi-objective multi-item fixed-charge solid transportation problem under twofold uncertainty. Neural Comput. Appl, vol. 31, no. 12, pp. 8593–8613.
  2. B. Tirkolaee, A. Goli, and G.-W. Weber, (2020). Fuzzy mathematical programming and self-adaptive artificial fish swarm algorithm for just-in-time energy-aware flow shop scheduling problem with outsourcing option. IEEE Trans. fuzzy Syst, vol. 28, no. 11, pp. 2772–2783.
  3. Saffarian, M. Niksirat, and S. M. Kazemi, (2021). A Hybrid Genetic-Simulated Annealing-Auction Algorithm for a Fully Fuzzy Multi-Period Multi-Depot Vehicle Routing Problem. Int. J. Supply Oper. Manag, vol. 8, no. 2, pp. 96–113.
  4. Heilpern, (1992). The expected value of a fuzzy number. Fuzzy Sets Syst, vol. 47, no. 1, pp. 81–86.
  5. Sakawa and R. Kubota, (2000). Fuzzy programming for multi objective job shop scheduling with fuzzy processing time and fuzzy due date through genetic algorithms. Eur. J. Oper. Res, vol. 120, no. 2, pp. 393–407.
International Journal of Supply and Operations Management
Volume 10, Issue 3
August 2023
Pages 319-336

Files

Share

How to cite

Statistics