A three-agent scheduling problem for minimizing the flow time on two machines

Lee, Wen-Chiung; Wang, Jen-Ya

RAIRO - Operations Research - Recherche Opérationnelle, Tome 54 (2020) no. 2, pp. 307-323.

Suite au passage du modèle économique de la revue en S20, le texte intégral des articles des années 2019 et 2020 est accessible uniquement sur le site de l'éditeur et est réservé aux abonnés.

This study introduces a two-machine three-agent scheduling problem. We aim to minimize the total tardiness of jobs from agent 1 subject to that the maximum completion time of jobs from agent 2 cannot exceed a given limit and that two maintenance activities from agent 3 must be conducted within two maintenance windows. Due to the NP-hardness of this problem, a genetic algorithm (named GA⁺) is proposed to obtain approximate solutions. On the other hand, a branch-and-bound algorithm (named B&B) is developed to generate the optimal solutions. When the problem size is small, we use B&B to verify the solution quality of GA⁺. When the number of jobs is large, a relative deviation is proposed to show the gap between GA⁺ and another ordinary genetic algorithm. Experimental results show that the proposed genetic algorithm can generate approximate solutions by consuming reasonable execution time.

[1] A. Agnetis, G. De Pascale and D. Pacciarelli, A Lagrangian approach to single-machine scheduling problems with two competing agents. J. Scheduling 12 (2009) 401–415. | DOI | MR | Zbl

[2] F. Ahmadizar and J. Eteghadipour, Single-machine earliness-tardiness scheduling with two competing agents and idle time. Eng. Optim. 49 (2017) 499–512. | DOI | MR

[3] K.R. Baker and J.C. Smith, A multiple-criterion model for machine scheduling. J. Scheduling 6 (2003) 7–16. | DOI | MR | Zbl

[4] S. Bouzidi-Hassini, F.B.S. Tayeb, F. Marmier and M. Rabahi, Considering human resource constraints for real joint production and maintenance schedules. Comput. Ind. Eng. 90 (2015) 197–211. | DOI

[5] X.L. Cao, W.H. Wu, W.H. Wu and C.C. Wu, Some two-agent single-machine scheduling problems to minimize minmax and minsum of completion times. Oper. Res. 18 (2018) 293–314.

[6] W.J. Chen, Scheduling of jobs and maintenance in a textile company. Int. J. Adv. Manuf. Technol. 31 (2007) 737–742. | DOI

[7] W.J. Chen, Scheduling with dependent setups and maintenance in a textile company. Comput. Ind. Eng. 57 (2009) 867–873. | DOI

[8] T.C.E. Cheng, C.Y. Liu, W.C. Lee and M. Ji, Two-agent single-machine scheduling to minimize the weighted sum of the agents’ objective functions. Comput. Ind. Eng. 78 (2014) 66–73. | DOI

[9] M.B. Cheng, P.R. Tadikamalla, J. Shang and B.X. Zhang, Two-machine flow shop scheduling with deteriorating jobs: minimizing the weighted sum of makespan and total completion time. J. Oper. Res. Soc. 66 (2015) 709–719. | DOI

[10] S.R. Cheng, Y.Q. Yin, C.H. Wen, W.C. Lin, C.C. Wu and J. Liu, A two-machine flowshop scheduling problem with precedence constraint on two jobs. Soft Comput. 21 (2017) 2091–2103. | DOI | Zbl

[11] S. Gawiejnowicz, W.C. Lee, C.L. Lin and C.C. Wu, Single-machine scheduling of proportionally deteriorating jobs by two agents. J. Oper. Res. Soc. 62 (2011) 1983–1991. | DOI

[12] D.E. Goldberg and R. Lingle, Alleles, loci and the traveling salesman problem. In: Proceedings of an International Conference on Genetic Algorithms and Their Application, Hillsdale, NJ, USA (1985). | Zbl

[13] L. Grigoriu and D. Briskorn, Scheduling jobs and maintenance activities subject to job-dependent machine deteriorations. J. Scheduling 20 (2017) 183–197. | DOI | MR | Zbl

[14] M.Z. Gu, J.W. Gu and X.W. Lu, An algorithm for multi-agent scheduling to minimize the makespan on $m$ parallel machines. J. Scheduling 21 (2018) 483–492. | DOI | MR | Zbl

[15] M. Haouari and M. Kharbeche, An assignment-based lower bound for a class of two-machine flow shop problems. Comput. Oper. Res. 40 (2013) 1693–1699. | DOI | MR | Zbl

[16] R. Jamshidi and M.M.S. Esfahani, Reliability-based maintenance and job scheduling for identical parallel machines. Int. J. Prod. Res. 53 (2015) 1216–1227. | DOI

[17] B. Jeong and Y.D. Kim, Minimizing total tardiness in a two-machine re-entrant flowshop with sequence-dependent setup times. Comput. Oper. Res. 47 (2014) 72–80. | DOI | MR | Zbl

[18] V. Kachitvichyanukul, Comparison of three evolutionary algorithms: GA, PSO, and DE. Ind. Eng. Manage. Syst. 11 (2012) 215–223.

[19] Y.D. Kim, A new branch and bound algorithm for minimizing mean tardiness in 2-machine flowshops. Comput. Oper. Res. 20 (1993) 391–401. | DOI | MR | Zbl

[20] J.Y. Lee and Y.D. Kim, 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. 66 (2015) 1542–1554. | DOI

[21] W.C. Lee and J.Y. Wang, A scheduling problem with three competing agents. Comput. Oper. Res. 51 (2014) 208–217. | DOI | MR | Zbl

[22] W.C. Lee and J.Y. Wang, A three-agent scheduling problem for minimizing the makespan on a single machine. Comput. Ind. Eng. 106 (2017) 147–160. | DOI

[23] W.C. Lee and C.C. Wu, Minimizing the total flow time and the tardiness in a two-machine flow shop. Int. J. Syst. Sci. 32 (2001) 365–373. | DOI | MR | Zbl

[24] W.C. Lee, S.K. Chen and C.C. Wu, Branch-and-bound and simulated annealing algorithms for a two-agent scheduling problem. Expert Syst. App. 37 (2010) 6594–6601. | DOI

[25] W.C. Lee, Y.H. Chung and M.C. Hu, Genetic algorithms for a two-agent single-machine problem with release time. Appl. Soft Comput. 12 (2012) 3580–3589. | DOI

[26] W.C. Lee, J.Y. Wang and H.W. Su, Algorithms for single-machine scheduling to minimize the total tardiness with learning effects and two competing agents. Concurrent Eng.-Res. App. 23 (2015) 13–26. | DOI

[27] W.C. Lee, J.Y. Wang and M.C. Lin, A branch-and-bound algorithm for minimizing the total weighted completion time on parallel identical machines with two competing agents. Knowl.-Based Syst. 105 (2016) 68–82. | DOI

[28] D.M. Lei, Variable neighborhood search for two-agent flow shop scheduling problem. Comput. Ind. Eng. 80 (2015) 125–131. | DOI

[29] B.M.T. Lin, F.J. Hwang and J.N.D. Gupta, Two-machine flowshop scheduling with three-operation jobs subject to a fixed job sequence. J. Scheduling 20 (2017) 293–302. | DOI | MR | Zbl

[30] P. Liu, N. Yi, X.Y. Zhou and H. Gong, Scheduling two agents with sum-of-processing-times-based deterioration on a single machine. Appl. Math. Comput. 219 (2013) 8848–8855. | MR | Zbl

[31] M. Liu, S.J. Wang, C.B. Chu and F. Chu, An improved exact algorithm for single-machine scheduling to minimise the number of tardy jobs with periodic maintenance. Int. J. Prod. Res. 54 (2016) 3591–3602. | DOI

[32] E.G. Lopez, M. O’Neill, On the effects of locality in a permutation problem: the Sudoku puzzle. In: IEEE Symposium on Computational Intelligence and Games. Milano, Italy (2009) 80–87.

[33] S.A. Mansouri and E. Aktas, Minimizing energy consumption and makespan in a two-machine flowshop scheduling problem. J. Oper. Res. Soc. 67 (2016) 1382–1394. | DOI

[34] B. Mor and G. Mosheiov, Minimizing maximum cost on a single machine with two competing agents and job rejection. J. Oper. Res. Soc. 67 (2016) 1524–1531. | DOI

[35] Y.D. Ni and Z.J. Zhao, Two-agent scheduling problem under fuzzy environment. J. Intell. Manuf. 28 (2017) 739–748. | DOI

[36] J.C.H. Pan, J.S. Chen and C.M. Chao, Minimizing tardiness in a two-machine flow-shop. Comput. Oper. Res. 29 (2002) 869–885. | DOI | MR | Zbl

[37] K. Rustogi and V.A. Strusevich, Single machine scheduling with time-dependent linear deterioration and rate-modifying maintenance. J. Oper. Res. Soc. 66 (2015) 500–515. | DOI

[38] J. Schaller, Note on minimizing total tardiness in a two-machine flowshop. Comput. Oper. Res. 32 (2005) 3273–3281. | DOI | MR | Zbl

[39] D. Shabtay, O. Dover and M. Kaspi, Single-machine two-agent scheduling involving a just-in-time criterion. Int. J. Prod. Res. 53 (2015) 2590–2604. | DOI

[40] Y.R. Shiau, W.C. Lee, Y.S. Kung and J.Y. Wang, A lower bound for minimizing the total completion time of a three-agent scheduling problem. Inf. Sci. 340 (2016) 305–320. | DOI | MR | Zbl

[41] J.M.P. Siopa, J.E.S. Garção and J.M.E. Silva, Component redundancy allocation in optimal cost preventive maintenance scheduling. J. Oper. Res. Soc. 66 (2015) 925–935. | DOI

[42] L.H. Su and H.M. Wang, Minimizing total absolute deviation of job completion times on a single machine with cleaning activities. Comput. Ind. Eng. 103 (2017) 242–249. | DOI

[43] K. Thornblad, A.B. Stromberg, M. Patriksson and T. Almgren, Scheduling optimisation of a real flexible job shop including fixture availability and preventive maintenance. Eur. J. Ind. Eng. 9 (2015) 126–145. | DOI

[44] M. Torkashvand, B. Naderi and S.A. Hosseini, Modelling and scheduling multi-objective flow shop problems with interfering jobs. Appl. Soft Comput. 54 (2017) 221–228. | DOI

[45] J.Y. Wang, A branch-and-bound algorithm for minimizing the total tardiness of a three-agent scheduling problem considering the overlap effect and environmental protection. IEEE Access 7 (2019) 5106–5123. | DOI

[46] J.Y. Wang, Minimizing the total weighted tardiness of overlapping jobs on parallel machines with a learning effect. J. Oper. Res. Soc. Accepted (2019). https://doi.org/10.1080/01605682.2019.1590511.

[47] D.J. Wang, Y.Q. Yin, J.Y. Xu, W.H. Wu, S.R. Cheng and C.C. Wu, Some due date determination scheduling problems with two agents on a single machine. Int. J. Prod. Econ. 168 (2015) 81–90. | DOI

[48] J.Q. Wang, G.Q. Fan, Y.Q. Zhang, C.W. Zhang and J.Y.T. Leung, Two-agent scheduling on a single parallel-batching machine with equal processing time and non-identical job sizes. Eur. J. Oper. Res. 258 (2017) 478–490. | DOI | MR | Zbl

[49] D.J. Wang, Y.Q. Yin, W.H. Wu, W.H. Wu, C.C. Wu and P.H. Hsu, A two-agent single-machine scheduling problem to minimize the total cost with release dates. Soft Comput. 21 (2017) 805–816. | DOI | Zbl

[50] W.H. Wu, Y.Q. Yin, T.C.E. Cheng, W.C. Lin, J.C. Chen, S.Y. Luo and C.C. Wu, A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect. J. Oper. Res. Soc. 68 (2017) 111–120. | DOI

[51] Z.J. Xu and D.H. Xu, Single-machine scheduling with preemptive jobs and workload-dependent maintenance durations. Oper. Res. 15 (2015) 423–436.

[52] C.N. Yang, B.M.T. Lin, F.J. Hwang and M.C. Wang, Acquisition planning and scheduling of computing resources. Comput. Oper. Res. 76 (2016) 167–182. | DOI | MR | Zbl

[53] J.F. Ye and H.M. Ma, Multiobjective joint optimization of production scheduling and maintenance planning in the flexible job-shop problem. Math. Probl. Eng. 2015 (2015) 725460. | Zbl

[54] Y.Q. Yin, C.C. Wu, W.H. Wu, C.J. Hsu and W.H. Wu, A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents. Appl. Soft Comput. 13 (2013) 1042–1054. | DOI

[55] Y.Q. Yin, D.S. Ye and G.C. Zhang, Single machine batch scheduling to minimize the sum of total flow time and batch delivery cost with an unavailability interval. Inf. Sci. 274 (2014) 310–322. | DOI | MR | Zbl

[56] Y.Q. Yin, Y. Wang, T.C.E. Cheng, D.J. Wang and C.C. Wu, Two-agent single-machine scheduling to minimize the batch delivery cost. Comput. Ind. Eng. 92 (2016) 16–30. | DOI

[57] A.J. Yu and J. Seif, Minimizing tardiness and maintenance costs in flow shop scheduling by a lower-bound-based GA. Comput. Ind. Eng. 97 (2016) 26–40. | DOI

[58] X.Y. Yu, Y.L. Zhang, D.H. Xu and Y.Q. Yin, Single machine scheduling problem with two synergetic agents and piece-rate maintenance. Appl. Math. Modell. 37 (2013) 1390–1399. | DOI | MR | Zbl

[59] F. Zammori, M. Braglia and D. Castellano, Harmony search algorithm for single-machine scheduling problem with planned maintenance. Comput. Ind. Eng. 76 (2014) 333–346. | DOI

[60] X.G. Zhang, Y.Q. Yin and C.C. Wu, Scheduling with non-decreasing deterioration jobs and variable maintenance activities on a single machine. Eng. Optim. 49 (2017) 84–97. | DOI | MR