Scheduling of periodic services to customers in dispersed locations from heterogeneous multi-agent companies considering uncertainty: A real case stud

Document Type : Article


1 Department of Industrial Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran

2 Department of Industrial Management and Information Technology, Management and Accounting Faculty, Shahid Beheshti University, G.C., Tehran, Iran


The scheduling problem of periodic services from service providers to customers located in different places and need different services. The service centers are also located in different positions, each of which has limited number of teams with the capability of performing one or some services. The goal is to simultaneously minimize ‘total service costs’ and ‘total earliness/tardiness’ in providing services to customers. Providing an optimal maintenance schedule is a big challenge in those companies with dispersed supply centers. In this paper, a novel bi-objective mixed integer linear programming model along with augmented epsilon constraint method is presented to exactly solve this problem. Then, a bi-objective meta-heuristic technique based on genetic algorithm is proposed and its performance in solving large-scaled problems is assessed. The uncertain parameters are faced through robust possibilistic programming approach to diminish the risk of decision making. Finally, the performance of the proposed model and solution approaches are evaluated through a real case study in maintenance scheduling of CNG stations equipment in Iran.


1. Behnamian, J. and Ghomi, S.F., "The heterogeneous multi-factory production network scheduling with adaptive communication policy and parallel machine".Information Sciences. 219, pp. 181-196 (2013).
2. Wu, T.-H., Chang, C.-C., and Chung, S.-H., "A simulated annealing algorithm for manufacturing cell formation problems".Expert Systems with Applications. 34(3), pp. 1609-1617 (2008).
3. Niwas, R. and Garg, H., "An approach for analyzing the reliability and profit of an industrial system based on the cost free warranty policy".Journal of the Brazilian Society of Mechanical Sciences and Engineering. 40(5), pp. 265 (2018).
4. Wu, S.-j., Gebraeel, N., Lawley, M.A., and Yih, Y., "A neural network integrated decision support system for condition-based optimal predictive maintenance policy".IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans. 37(2), pp. 226-236 (2007).
5. Vasili, M., Hong, T.S., Ismail, N., and Vasili, M., "Maintenance optimization models: a review and analysis".optimization. 1(2) (2011).
6. Al-Najjar, B., "The lack of maintenance and not maintenance which costs: A model to describe and quantify the impact of vibration-based maintenance on company's business".International Journal of Production Economics. 107(1), pp. 260-273 (2007).
7. Al-Najjar, B. and Alsyouf, I., "Enhancing a company's profitability and competitiveness using integrated vibration-based maintenance: A case study".European journal of operational research. 157(3), pp. 643-657 (2004).
8. Kathleen, E.M. and Elliott, N.W., "TOTAL PRODUCTIVE MAINTENANCE (TPM)".Encyclopedia of Production and Manufacturing Management, pp. 796-803 (2000).
9. Vineyard, M., Amoako-Gyampah, K., and Meredith, J.R., "An evaluation of maintenance policies for flexible manufacturing systems: a case study".International Journal of Operations & Production Management. 20(4), pp. 409-426 (2000).
10. Chung, S., Lau, H.C., Choy, K., Ho, G.T., and Tse, Y., "Application of genetic approach for advanced planning in multi-factory environment".International Journal of Production Economics. 127(2), pp. 300-308 (2010).
11. Doostparast, M., Kolahan, F., and Doostparast, M., "Optimisation of PM scheduling for multi-component systems–a simulated annealing approach".International Journal of Systems Science. 46(7), pp. 1199-1207 (2015).
12. Ebrahimipour, V., Najjarbashi, A., and Sheikhalishahi, M., "Multi-objective modeling for preventive maintenance scheduling in a multiple production line".Journal of Intelligent Manufacturing. 26(1), pp. 111-122 (2015).
13. Ovacik, I.M. and Uzsoy, R.,Decomposition methods for complex factory scheduling problems. Springer Science & Business Media.(2012).
14. Lee, H., "Heuristic for scheduling on nonidentical machines to minimize tardy jobs".International Journal of Industrial Engineering: Theory Applications and Practice. 7(3), pp. 188-194 (2000).
15. Balakrishnan, N., Kanet, J.J., and Sridharan, V., "Early/tardy scheduling with sequence dependent setups on uniform parallel machines".Computers & Operations Research. 26(2), pp. 127-141 (1999).
16. Zhu, Z. and Heady, R.B., "Minimizing the sum of earliness/tardiness in multi-machine scheduling: a mixed integer programming approach".Computers & Industrial Engineering. 38(2), pp. 297-305 (2000).
17. Rocha, P.L., Ravetti, M.G., Mateus, G.R., and Pardalos, P.M., "Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and machine-dependent setup times".Computers & Operations Research. 35(4), pp. 1250-1264 (2008).
18. Ruiz, R., Andrés, C., Baptiste, P., Kendall, G., Munier-Kordon, A., and Sourd, F. "Unrelated parallel machines scheduling with resource-assignable sequence dependent setup times. in Proceedings of the 3rd Multidisciplinary International Conference on Scheduling", Theory and Applications (MISTA), (2007).
19. Kanyalkar, A. and Adil*, G., "An integrated aggregate and detailed planning in a multi-site production environment using linear programming".International Journal of Production Research. 43(20), pp. 4431-4454 (2005).
20. Kerkhove, L.-P. and Vanhoucke, M., "Scheduling of unrelated parallel machines with limited server availability on multiple production locations: a case study in knitted fabrics".International Journal of Production Research. 52(9), pp. 2630-2653 (2014).
21. Behnamian, J. and Ghomi, S.F., "A survey of multi-factory scheduling".Journal of Intelligent Manufacturing. 27(1), pp. 231-249 (2016).
22. Woo, Y.-B., Jung, S., and Kim, B.S., "A rule-based genetic algorithm with an improvement heuristic for unrelated parallel machine scheduling problem with time-dependent deterioration and multiple rate-modifying activities".Computers & Industrial Engineering. 109, pp. 179-190 (2017).
23. Mensendiek, A., Gupta, J.N., and Herrmann, J., "Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness".European Journal of Operational Research. 243(2), pp. 514-522 (2015).
24. Poursabzi, O., Mohammadi, M., and Naderi, B., "An improved model and a heuristic for capacitated lot sizing and scheduling in job shop problems".Scientia Iranica. 25(6), pp. 3667-3684 (2018).
25. Asadi-Gangraj, E., "Lagrangian relaxation approach to minimizing makespan in hybrid flow shop scheduling problem with unrelated parallel machines".SCIENTIA IRANICA. 25(6), pp. 3765-3775 (2018).
26. Dieter, A., Pickard, K., and Bertsche, B., "Periodic renewal of spare parts using Weibull".Quality and Reliability Engineering International. 26(3), pp. 193-198 (2010).
27. Garg, H., Rani, M., and Sharma, S., "Preventive maintenance scheduling of the pulping unit in a paper plant".Japan journal of industrial and applied mathematics. 30(2), pp. 397-414 (2013).
28. Garg, H. and Sharma, S.P., "A TWO-PHASE APPROACH FOR RELIABILITY AND MAINTAINABILITY ANALYSIS OF AN INDUSTRIAL SYSTEM".International Journal of Reliability, Quality and Safety Engineering. 19(03), pp. 1250013 (2012).
29. Hosseini, S., Kalam, S., Barker, K., and Ramirez-Marquez, J.E., "Scheduling multi-component maintenance with a greedy heuristic local search algorithm".Soft Computing, pp. 1-16 (2019).
30. Ji, M., He, Y., and Cheng, T.E., "Single-machine scheduling with periodic maintenance to minimize makespan".Computers & operations research. 34(6), pp. 1764-1770 (2007).
31. Simeu-Abazi, Z. and Ahmad, A.A., "Optimisation of distributed maintenance: Modelling and application to the multi-factory production".Reliability Engineering & System Safety. 96(11), pp. 1564-1575 (2011).
32. Xu, D., Sun, K., and Li, H., "Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan".Computers & operations research. 35(4), pp. 1344-1349 (2008).
33. Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., and Sassani, F., "Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints".Computers & Operations Research. 36(12), pp. 3224-3230 (2009).
34. Volkanovski, A., Mavko, B., Boševski, T., Čauševski, A., and Čepin, M., "Genetic algorithm optimisation of the maintenance scheduling of generating units in a power system".Reliability Engineering & System Safety. 93(6), pp. 779-789 (2008).
35. Kadri, R.L. and Boctor, F.F., "An efficient genetic algorithm to solve the resource-constrained project scheduling problem with transfer times: The single mode case".European Journal of Operational Research. 265(2), pp. 454-462 (2018).
36. Hosseinabadi, A.A.R., Vahidi, J., Saemi, B., Sangaiah, A.K., and Elhoseny, M., "Extended genetic algorithm for solving open-shop scheduling problem".Soft computing. 23(13), pp. 5099-5116 (2019).
37. Garg, H., "A hybrid GSA-GA algorithm for constrained optimization problems".Information Sciences. 478, pp. 499-523 (2019).
38. Su, C. and Liu, Y., "Multi-objective imperfect preventive maintenance optimisation with NSGA-II".International Journal of Production Research, pp. 1-17 (2019).
39. May, G., Stahl, B., Taisch, M., and Prabhu, V., "Multi-objective genetic algorithm for energy-efficient job shop scheduling".International Journal of Production Research. 53(23), pp. 7071-7089 (2015).
40. Dai, C., Cai, Y., Ren, W., Xie, Y., and Guo, H., "Identification of optimal placements of best management practices through an interval-fuzzy possibilistic programming model".Agricultural Water Management. 165, pp. 108-121 (2016).
41. Wan, S.-P. and Dong, J.-Y., "Possibility linear programming with trapezoidal fuzzy numbers".Applied Mathematical Modelling. 38(5-6), pp. 1660-1672 (2014).
42. Tanaka, H., Okuda, T., and Asai, K., "Fuzzy mathematical programming".Transactions of the Society of Instrument and Control Engineers. 9(5), pp. 607-613 (1973).
43. Pishvaee, M.S., Razmi, J., and Torabi, S.A., "Robust possibilistic programming for socially responsible supply chain network design: A new approach".Fuzzy sets and systems. 206, pp. 1-20 (2012).
44. Ehrgott, M.,"Multicriteria optimization", Springer Science & Business Media, (2005).
45. Marler, R.T. and Arora, J.S., "Survey of multi-objective optimization methods for engineering".Structural and multidisciplinary optimization. 26(6), pp. 369-395 (2004).
46. Mavrotas, G., "Effective implementation of the ε-constraint method in multi-objective mathematical programming problems".Applied mathematics and computation. 213(2), pp. 455-465 (2009).
47. Aghaei, J., Amjady, N., and Shayanfar, H.A., "Multi-objective electricity market clearing considering dynamic security by lexicographic optimization and augmented epsilon constraint method".Applied Soft Computing. 11(4), pp. 3846-3858 (2011).
48. Avalos-Rosales, O., Angel-Bello, F., and Alvarez, A., "Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times".The International Journal of Advanced Manufacturing Technology. 76(9-12), pp. 1705-1718 (2015).
49. Joo, C.M. and Kim, B.S., "Hybrid genetic algorithms with dispatching rules for unrelated parallel machine scheduling with setup time and production availability".Computers & Industrial Engineering. 85, pp. 102-109 (2015).
50. Kim, D.-W., Kim, K.-H., Jang, W., and Frank Chen, F., "Unrelated parallel machine scheduling with setup times using simulated annealing".Robotics and Computer-Integrated Manufacturing. 18(3), pp. 223-231 (2002).
51. Vallada, E. and Ruiz, R., "A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times".European Journal of Operational Research. 211(3), pp. 612-622 (2011).