Solving a multi-agent scheduling problem in a flow shop environment considering rejection and deteriorating jobs: using a meta-heuristic algorithm

Document Type : Research Paper

Authors

Department of Industrial Engineering, Shahed University, Tehran,

Abstract

A multi-agent scheduling problem in a flow shop environment has been considered in this study. Multi-agent scheduling problem is a subset of multi-objective scheduling problems in which each agent has a set of jobs and its aim is to optimize its own objective function. To make the proposed problem more realistic, two practical assumptions such as deteriorating jobs and rejection has been considered. A mixed integer programming model is presented for the problem. The main contribution of the proposed model is to consider multi-agent with two mentioned assumptions. Also, due to the complexity of the model and its inability to solve large-scale problems, a meta-heuristic Non-Dominated sorting Genetic Algorithm (NSGA-II) are developed. Obtained solutions of this algorithm are compared with exact augmented ε-constraint method and the results confirm its performance.

Keywords

Main Subjects

References

[1]       Pinedo, M., (2015). Scheduling. Springer.
[2]        Agnetis, A., Billaut, J.C., Gawiejnowicz, S., Pacciarelli, D., Souhal, A., (2014). “Multi-agent scheduling”. Berlin Heidelberg: Springer Berlin Heidelberg. doi, 10(1007): 978-3.
[3]       Wu, W.H., Yin, Y., Wu, W.H., Wu, C.C., Hsu, P.H. (2014). “A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents”, Journal of Industrial and Management Optimization, 10(2): 591-611.
[4]       Shabtay, D., Gaspar, N., Kaspi, M. (2013). “A survey on offline scheduling with rejection”, Journal of Scheduling, 16(1): 3-28.
[5]       Baker, K.R., Smith, J.C., (2003). “A multiple-criterion model for machine scheduling”, Journal of Scheduling, 6(1): 7-16.
[6]        Agnetis, A., Mirchandani, P.B., Pacciarelli, D., Pacifici, A. (2004). “Scheduling problems with two competing agents”, Operations Research, 52(2): 229-242.
[7]        Fan, B.Q., Cheng, T.C.E. (2016). “Two-agent scheduling in a flowshop”, European Journal of Operational Research, 252(2): 376-384.
[8]        Choi, J.Y. (2015). “Minimizing total weighted completion time under makespan constraint for two-agent scheduling with job-dependent aging effects”, Computers & Industrial Engineering, 83: 237-243.
[9]        Cheng, S.R., (2014). “Some new problems on two-agent scheduling to minimize the earliness costs”, International Journal of Production Economics, 156: 24-30.
[10]    Lei, D. (2015). “Variable neighborhood search for two-agent flow shop scheduling problem”, Computers & Industrial Engineering, 80: 125-131.
[11]    Lee, W.C., Chen, S.K., Chen, C.W., Wu, C.C. (2011). “A two-machine flowshop problem with two agents”, Computers & Operations Research, 38(1): 98-104.
[12]    Shiau, Y.R., Lee, W.C., Kung, Y.S., Wang, J.Y. (2016). “A lower bound for minimizing the total completion time of a three-agent scheduling problem”, Information Sciences, 340: 305-320.
[13]    Kunnathur, A.S., Gupta, S.K. (1990). “Minimizing the makespan with late start penalties added to processing times in a single facility scheduling problem”, European Journal of Operational Research, 47(1): 56-64.
[14]    Cheng, T.C.E., Lee, W.C., Wu, C.C. (2010). “Single-machine scheduling with deteriorating functions for jobs procedding times”, Applied Mathematical Modeling, 34(12): 4171-4178.
[15]    Yin, Y., Cheng, T.C.E., Wan, L., Wu, C.C.,  Liu, J. (2015). “Two-agent single-machine scheduling with deteriorating jobs”, Computers and Industrial Engineering, 81: 177-185.
[16]    Lee, W.C., Wang, W.J., Shiau, Y.R. Wu, C.C. (2010). “A single machine scheduling problem with two agent and deteriorating jobs”, Applied Mathematical Modeling, 34(10): 3098-3107.
[17]    Bartal, Y., Leonardi, S., Marchetti-Spaccamela, A., Sgall, J., Stougie, L. (2000). “Multiprocessor scheduling with rejection”, SIAM Journal on Discrete Mathematics, 13(1): 64-78.
[18]    Feng, Q., Fan, B., Li, S., Shang, W., (2015). “Two-agent scheduling with rejection on a single machine”, Applied Mathematical Modelling, 39(3): 1183-1193.
[19]    Li, S., Yuan, J., (2010). “Parallel-machine scheduling with deteriorating jobs and rejection”, Theoretical Computer Science, 411(40): 3642-3650.
[20]    Wu, C.C., Lee, W.C., (2008). “Single-machine group-scheduling problems with deteriorating setup times and job-processing times”, International Journal of Production Economics, 115(1): 128-133.
[21]    Chen, D.S., Batson, R.G., Dang, Y., (2010). “Applied integer programming: modeling and solution”,1st edition, John Wiley & Sons.
[22]    Sadjadi, S.J., Heidari, M., Esboei, A.A., (2014). “Augmented ε-constraint method in multi objective staff scheduling problem: a case study”, The International Journal of Advanced Manufacturing Technology, 70(5-8): 1505-1514.
[23]    Ciro, G.C., Dugardin, F., Yalaoui, F., Kelly, R., (2016). “A NSGA-II and NSGA-III comparison for solving an open shop scheduling problem with resource constraints”, IFAC-Papers Online, 49(12): 1272-1277.
[24]    Asefi, H., Jolai, F., Rabiee, M., Araghi, M.T., (2014). “A hybrid NSGA-II and VNS for solving a bi-objective no-wait flexible flowshop scheduling problem”, The International Journal of Advanced Manufacturing Technology, 75(5-8): 1017-1033.
[25]    Zitzler, E., Deb, K., Thiele, L. (2000). “Comparison of multiobjective evolutionary algorithms: Empirical results”, Evolutionary computation, 8(2): 173-195.
[26]    Zitzler, E., Deb, K., Thiele, L. (2000). “Comparison of multiobjective evolutionary algorithms: Empirical results”, Evolutionary computation, 8(2): 173-195.
[27]    Goh, C.K., Tan, K.C., Liu, D.S., Chiam, S.C., (2010). “A competitive and cooperative co-evolutionary approach to multi-objective particle swarm optimization algorithm design”, European Journal of Operational Research, 202(1): 42-54.
Journal of Industrial Engineering Research in Production Systems
Volume 5, Issue 10
July 2017
Pages 17-29

Files

Share

How to cite

Statistics