Chance-constrained model for uncertain job shop scheduling problem.

*(English)*Zbl 1370.90120Summary: Job shop scheduling problem is well-investigated and widely applied in the fields of operational research, system engineering and automatic management. This paper employs uncertain programming to deal with the job shop scheduling problem with uncertain processing time and cost. First, a chance-constrained model is proposed under the framework of uncertainty theory. The model is equivalent to a crisp one by inverse uncertainty distribution method. Furthermore, three heuristic algorithms (genetic algorithm, particle swarm optimization, firefly algorithm) are employed for solving the model. Finally, a numerical example is solved by these three algorithms, and the results are analyzed to show which algorithm is better for solving the established model.

##### MSC:

90B35 | Deterministic scheduling theory in operations research |

##### Keywords:

job shop scheduling; uncertain programming; chance-constrained model; inverse uncertainty distribution method; heuristic algorithm
PDF
BibTeX
Cite

\textit{J. Shen} and \textit{Y. Zhu}, Soft Comput. 20, No. 6, 2383--2391 (2016; Zbl 1370.90120)

Full Text:
DOI

##### References:

[1] | Ashour, S, A decomposition approach for the machine scheduling problem, Int J Prod Res, 6, 109-122, (1967) |

[2] | Aphirak, K; Sirikarn, C; Thatchai, T; Peeraya, T; Warattapop, C; Pupong, P, Application of firefly algorithm and its parameter setting for job shop scheduling, J Ind Technol, 8, 89-97, (2012) |

[3] | Bin, Q; Ling, W; Xian, H; Xiong, W, Multi-objective no-wait flow-shop scheduling with a memetic algorithm based on differential evolution, Soft Comput, 13, 847-869, (2009) |

[4] | Binchao, C; Timothy, I, A flexible dispatching rule for minimizing tardiness in job shop scheduling, Int J Prod Econ, 144, 360-365, (2013) |

[5] | Boxma, O; Forst, F, Minimizing the expected weighted number of tardy jobs in stochastic flow shops, Oper Res Lett, 5, 119-126, (1986) · Zbl 0633.90028 |

[6] | Conway R, Maxwell W, Miller L (1967) Theory of scheduling. Addison-Wesltey, Massachusetts · Zbl 1058.90500 |

[7] | Ding, C; Zhu, Y, Two empirical uncertain models for project scheduling problem, J Oper Res Soc, (2014) |

[8] | Ding, S, Uncertain minimum cost flow problem, Soft Comput, 18, 2201-2207, (2014) · Zbl 1330.90014 |

[9] | Fisher, M, A dual algorithm for the one-machine scheduling problem, Math Program, 11, 229-251, (1976) · Zbl 0359.90039 |

[10] | Gao, Y, Uncertain models for single facility location problems on networks, Appl Math Model, 36, 2592-2599, (2012) · Zbl 1246.90083 |

[11] | Gao, Y; Yang, L; Li, S; Kar, S, On distribution function of the diameter in uncertain graph, Inf Sci, 296, 61-74, (2015) · Zbl 1360.05131 |

[12] | Graham, R; Lawler, E; Lensra, J; Rinnooy, K, Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann Discret Math, 5, 287-326, (1979) · Zbl 0411.90044 |

[13] | Hodegson, T, A note on single machine sequencing with random processing time, Manag Sci, 23, 1144-1146, (1977) · Zbl 0367.90075 |

[14] | Ishii, H; Tada, M; Masuda, T, Two scheduling problems with fuzzy due-dates, Fuzzy Sets Syst, 46, 339-347, (1992) · Zbl 0767.90037 |

[15] | Johnson, S, Optimal two and three-stage production schedules with setup times included, Nav Res Logist Q, 1, 61-68, (1954) · Zbl 1349.90359 |

[16] | Kennedy J, Eberhart R (1995) Particle swarm optimization. In: Proceedings of the 1995 IEEE international conference on neural networks, vol 4, 1942-1948 · Zbl 0741.90037 |

[17] | Kerem, B, A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem, Comput Oper Res, 38, 967-983, (2011) · Zbl 1205.90116 |

[18] | Miguel, Á; Inés, G; Camino, R; Ramiro, V, An efficient hybrid evolutionary algorithm for scheduling with setup times and weighted tardiness minimization, Soft Comput, 16, 2097-2113, (2012) |

[19] | Lawler, E, Optimal sequencing of a single machine subject to precedence constraints, Manag Sci, 19, 544-546, (1973) · Zbl 0254.90039 |

[20] | Lei D (2007) Pareto archive particle swarm optimization for multi-objective fuzzy job shop scheduling problems. Int J Adv Manuf Technol 37(1):157C165 · Zbl 0359.90039 |

[21] | Liu B (2007) Uncertainty theory, 2nd edn. Springer-Verlag, Berlin · Zbl 1141.28001 |

[22] | Liu B (2009) Theory and practice of uncertain programming, 2nd edn. Springer-Verlag, Berlin · Zbl 1158.90010 |

[23] | Liu B (2010) Uncertainty theory: a branch of mathematics for modeling human uncertainty. Springer-Verlag, Berlin |

[24] | Nabeshima, I, General scheduling algorithms with applications to parallel scheduling and multiprogramming scheduling, J Oper Res Soc Jpn, 14, 72-99, (1971) · Zbl 0247.90030 |

[25] | Prade, H, Using fuzzy set theory in a scheduling problem: a case study, Fuzzy Sets Syst, 2, 153-165, (1979) · Zbl 0403.90036 |

[26] | Peng, J; Liu, B, Parallel machine scheduling models with fuzzy processing times, Inf Sci, 1, 49-66, (2004) · Zbl 1101.68424 |

[27] | Pinedo, M, Stochastic scheduling with release dates and due dates, Oper Res, 31, 559-572, (1983) · Zbl 0523.90046 |

[28] | Rui, Z; Shiji, S; Cheng, W, A two-stage hybrid particle swarm optimization algorithm for the stochastic job shop scheduling problem, Knowl-Based Syst, 27, 393-406, (2012) |

[29] | Sarin, S; Erel, E; Steiner, C, Sequencing jobs on a single machine with a common due date and stochastic processing times, Eur J Oper Res, 51, 188-198, (1991) · Zbl 0741.90037 |

[30] | Thiagarajan, S; Rajendran, C, Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs, Comput Ind Eng, 49, 463-503, (2005) |

[31] | Yang, X, Firefly algorithms for multimodal optimization, Lect Notes Comput Sci, 5972, 169-178, (2009) · Zbl 1260.90164 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.