Stable scheduling of single machine with probabilistic parameters

• Autorzy: Bożejko W. , Rajba P. , Wodecki M.

Identyfikatory

DOI

10.1515/bpasts-2017-0026

• Języki publikacji: EN

Abstrakty

EN

We consider a stochastic variant of the single machine total weighted tardiness problem jobs parameters are independent random variables with normal or Erlang distributions. Since even deterministic problem is NP-hard, it is difficult to find global optimum for large instances in the reasonable run time. Therefore, we propose tabu search metaheuristics in this work. Computational experiments show that solutions obtained by the stochastic version of metaheuristics are more stable (i.e. resistant to data disturbance) than solutions generated by classic, deterministic version of the algorithm.

Słowa kluczowe

EN

scheduling; uncertain parameters; tabu search; stability

PL

planowanie; niepewne parametry; stabilność; przeszukiwanie tabu

• Wydawca: Polska Akademia Nauk, Wydział IV Nauk Technicznych
• Czasopismo: Bulletin of the Polish Academy of Sciences. Technical Sciences
• Rocznik: 2017
• Tom: Vol. 65, nr 2
• Strony: 219--231
• Opis fizyczny: Bibliogr. 30 poz., tab.

Twórcy

autor

Bożejko W.

• Department of Control Systems and Mechatronics, Faculty of Electronics, Wrocław University of Science and Technology, Wyb. Wyspiańskiego, 50-370 Wrocław, Poland

autor

Rajba P.

• Institute of Computer Science, University of Wrocław, 15 Joliot-Curie St., 50-383 Wrocław, Poland

autor

Wodecki M.

• Institute of Computer Science, University of Wrocław, 15 Joliot-Curie St., 50-383 Wrocław, Poland

Bibliografia

• [1] B. Alidee, I. Dragon, “A note on minimizing the weighted sum of tardy and early completion penalties in a single machine”, Journal of Operational Research 96 (3), 559-563 (1997).
• [2] W. Bożejko, J. Grabowski, M. Wodecki, “Block approach-tabu search algorithm for single machine total weighted tardiness problem”, Computers & Industrial Engineering 50, 1-14 (2006).
• [3] W. Bożejko, M. Wodecki, “On the theoretical properties of swap multimoves”, Operations Research Letters 35(2), 227-231 (2007).
• [4] W. Bożejko, “Parallel path relinking method for the single machine total weighted tardiness problem with sequence-dependent setups”, Journal of Intelligent Manufacturing 21(6), 777-785 (2010).
• [5] X. Cai, X. Zhou, “Single-machine scheduling with expotential processing times and general stochastic cost functions”, Journal of Global Optimization 31, 317-332 (2005).
• [6] X. Cai, X. Wu, X. Zhou, “Optimal stochastic scheduling”, International Series in Operations Research & Management Science 207, Springer, 2014.
• [7] H.A.J. Crauwels, C.N. Potts, L.N. Van Wassenhove, “Local search heuristics for the single machine total weighted tardiness scheduling problem”, INFORMS Journal on Computing 10(3), 341-350 (1998).
• [8] B.C. Dean, “Approximation algorithms for stochastic scheduling problems”, PhD thesis, Massachusetts Institute of Technology (2005).
• [9] M.T. Den Basten, M. Stützle, M. Dorigo, “Design of iterated local search algoritms. An example application to the single machine total weighted tardiness problem”, J.W.Boers et al. (eds.) Evo Worskshop 2001, Lecture Notes in Computer Science 2037, 441-451 (2001).
• [10] A. Elyasi, N. Salmasi, “Stochastic scheduling with minimizing the number of tardy jobs using chance constrained programming”, Mathematical and Computer Modeling 57, 1154-1164 (2013).
• [11] Hu, K., Zhang, X., Gen, M., Jo J., “A new model for single machine scheduling with uncertain processing time”, Journal of Intelligent Manufacturing, DOI 10.1007/s10845‒015‒1033‒9, 1-9 (2015).
• [12] W. Jang, “Dynamic scheduling of stochastic jobs a single machine”, European Journal of Operational Research, 138, 518-503 (2002).
• [13] G. Kirlik, C. Oguz, “A variable neighbourhood search for minimizing total weighted tardiness with sequence dependent setup times on a single machine”, Computers&Operatins Research 39, 1506-1520 (2012).
• [14] A. Lann, G. Mosheiov, “Single machine scheduling to minimize the number of early and tardy jobs”, Computers and Operations Research, 23(8), 769-781 (1996).
• [15] J.K. Lenstra, A.G.H. Rinnoy Kan, A.G.H., P.Brucker, “Complexity of machine scheduling problems”, Annals of Discrete Mathematics 1, 343-362 (1977).
• [16] W. Li, W.J. Braun, Y.Q. Zhao, “Stochastic scheduling on a repairable machine with Erlang uptime distribution”, Advances in Applied Probability 30(4), 1073-1088 (1998).
• [17] Y. Li, R. Chen, “Stochastic single machine scheduling to minimize the weighted number of tardy jobs”, B.-Y.Cao et al. (eds.): Fuzzy Information and Engineering, AISC, 363-368 (1998).
• [18] M.M Mazdeh., H. Hadad, P. Ghanbari, “Solving a single machine stochastic scheduling problem using a branch and bound algorithm and simulated annealing”, International Journal of Management Science and Engineering Management 7(2), 110-118 (2012).
• [19] M. Nawaz, E.E. Enscore, I. Ham, “A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem”, OMEGA 11(1), 91-95 (1983).
• [20] OR-Library https://files.nyu.edu/jeb21/public/jeb/info.html
• [21] M.L. Pinedo: Scheduling: Theory, Algorithms, and Systems, fourth edition, Springer New York Dordrecht Heidelberg London (2010).
• [22] C.N. Potts, L.N. Van Wassenhove, “A branch and bound algorithm for the total weighted tardiness problem”, Operations Research 33, 177-181 (1985).
• [23] C.N. Potts, L.N. Van Wassenhove, “Single machine tardiness sequencing heuristics”, IIE Transactions 23, 346-354 (1991).
• [24] W.E. Smith, “Various optimizers for single-stage production”, Naval Research Logist Quartely 3, 59-66 (1956).
• [25] H.M. Soroush, “Single machine scheduling with stochastic processing times or stochastic due-dates to minimize the number of early and tardy jobs”, International Journal of Operations Research 3(2), 90-108 (2006).
• [26] H.M. Soroush, “Minimizing the weighted number of early and tardy jobs in a stochasic single machine scheduling problem”, European Journal of Operational Research 181, 266-287 (2007).
• [27] J.M. Van den Akker, H. Hoogeveen, “Minimizing the number of late jobs in a stochastic setting using a chance constraint”, Journal of Scheduling 11, 59-69 (2008).
• [28] J. Vondrák, “Probabilistic methods in combinatorial and stochastic optimization”, PhD Thesis, MIT (2005).
• [29] M. Wodecki, “A branch-and-bound parallel algorithm for single- machine total weighted tardiness problem”, Advanced Manufacturing Technology 37, 996-1004 (2008).
• [30] M. Wodecki, “A block approach to earliness-tardiness scheduling problems”, International Journal on Advanced Manufacturing Technology 40, 797-807 (2009).

Uwagi

PL

Opracowanie ze środków MNiSW w ramach umowy 812/P-DUN/2016 na działalność upowszechniającą naukę (zadania 2017).