Scatter Search Based Algorithms for Min-Max Regret Task Scheduling Problems with Interval Uncertainty

• Autorzy: Jerzy Józefczyk , Marcin Siepak
• Języki publikacji: EN

Abstrakty

EN

Uncertain versions of three task scheduling problems: P║C_max, F2║C_max, R║Σ C_j are investigated. Parametric uncertainty is only considered which is represented by intervals. It is assumed that values of execution times of tasks are not a priori given, and they belong to the intervals of known bounds. No distributions additionally characterizing the uncertain parameters are assumed. The regret is used as the basis for a criterion evaluating the uncertainty. In a consequence, min-max regret combinatorial problems are solved. Heuristic algorithms based on Scatter Search are proposed. They are evaluated via computational experiments and compared to a simple middle intervals heuristics and to exact solutions for small instances of the problems considered. (original abstract)

Słowa kluczowe

EN

Algorithms; Task scheduling theory; Uncertainty; Operations research

PL

Algorytmy; Teoria szeregowania zadań; Niepewność; Badania operacyjne

• Czasopismo: Control and Cybernetics
• Rocznik: 2013
• Tom: 42
• Numer: nr 3
• Strony: 667--698

Twórcy

autor

Jerzy Józefczyk

• Wroclaw University of Technology

autor

Marcin Siepak

• Wroclaw University of Technology

Bibliografia

• Ayyub, B.M. and Klir, G.J. (2006) Uncertainty Modeling and Analysis in Engineering and the Sciences. Chapman&Hall/CRC, Boca Raton-London-New York.
• Aissi, H., Bazgan, C., Vanderpooten, D. (2005) Complexity of the min-max and min-max regret assignment problem. Operations Research Letters 33 (6), 634-640.
• Aissi, H., Bazgan, C., Vanderpooten, D. (2009) Min-max and min-max regret versions of combinatorial optimization problems: A survey. European Journal of Operational Research, 197(2), 427-438.
• Averbakh, I. (2000) Minimax regret solutions for minimax optimization problems with uncertainty. Operations Research Letters, 27(2), 57-65.
• Averbakh, I. and Pereira, J. (2011) Exact and heuristic algorithms for the interval data robust assignment problem. Computers & Operations Research, 38(8), 1153-1163.
• Bubnicki, Z. (2004) Analysis and Decision Making in Uncertain Systems. Springer Verlag, Berlin-London-New York.
• Conde, E. (2007) Minmax regret location-allocation problem on a Network under uncertainty. European Journal of Operational Research, 179(3), 1025-1039.
• Conde, E. (2009) A minmax regret approach to the critical path method with task interval times. European Journal of Operational Research, 197 (1), 235-242.
• Conde, E. (2010) A 2-approximation for minmax regret problems via a midpoint scenario optimal solution. Operations Research Letters, 38(4), 326-327.
• Corberan, A., Fernandez, A.E., Laguna, M., Marti, R. (2002) Heuristic solutions to the problem of routing school buses with multiple objectives. Journal of the Operational Research Society, 53, 427-435.
• Garey, M.R. and Johnson, D.S. (1978) Strong NP-completeness results: motivation, examples, and implications. J. Assoc. Comput. Mach. 25(3), 499-508.
• Glover, F. (1997) A template for scatter search and path relinking. In: Proceeding AE '97 Selected Papers from the Third European Conference on Artificial Evolution Nimes, France. IEEE Computer Society, 3-54.
• Glover, F., Laguna, M. and Marti, R.(2000) Fundamentals of scatter search and path relinking. Control & Cybernetics, 29(3), 653-684.
• Gutierrez, G.J., Kouvelis, P., Kurawarwala, A.A. (1996) A robust approach to uncapacitated network design problems. European Journal of Operational Research, 94 (2), 362-376.
• Johnson, S.M. (1954) Optimal two- and three-stage production Schedule with setup times included. Naval Research Logistics Quarterly, 1(1), 61-68.
• Jozefczyk, J. (2008) Worst-case allocation algorithms in a complex of operations with interval parameters. Kybernetes, 37, 652-676.
• Jozefczyk, J. and Siepak, M. (2011) Minmax regret algorithms for uncertain P║Cmax problem with interval processing times. In: H. Selvaraj and D. Zydek, eds., Proceedings of 21'st International Conference on Systems Engineering, Las Vegas, USA. IEEE Computer Society, Los Alamitos, 115-119.
• Jozefczyk, J. and Siepak, M. (2013) Worst-case regret algorithms for selected optimization problems with interval uncertainty. Kybernetes, 42 (3), 371-382.
• Jungnickel, D. (2008) Graphs, Networks and Algorithms. Springer, Berlin-Heidelberg-New York.
• Kasperski, A. (2008) Discrete Optimization with Interval Data: Minmax Regret and Fuzzy Approach. Studies in Fuzziness and Soft Computing. Springer, Berlin-Heidelberg-New York.
• Kasperski, A. and Zielinski, P. (2008) A 2-approximation algorithm for interval data minmax regret sequencing problems with the total flow time criterion. Operations Research Letters, 42, 343-344.
• Kasperski, A., Makuchowski, M., Zielinski, P. (2012) A tabu search algorithm for the minmax regret minimum spanning tree problem with interval data. Journal of Heuristics, 18(4), 593-625.
• Kasperski, A., Kurpisz, A., Zielinski, P. (2013) Approximating the min-max (regret) selecting items problem. Information Processing Letters, 113(1-2), 23-29.
• Klir, G.J. (2006) Uncertainty and Information: Foundations of Generalized Information Theory. Wiley.
• Kouvelis, P. and Yu, G. (1997) Robust Discrete Optimization and its Applications. Kluwer Academic Publishers, Dordrecht-Boston-London.
• Kouvelis, P., Daniels, R.L., Vairaktaris, G. (2000) Robust scheduling of a two-machine flow shop with uncertain processing times. IIE Transactions, 32(5), 421-432.
• Laguna, M. and Marti, R. (2003) Scatter Search-Methodology and Implementations. Kluwer Academic Publishers, Dortrecht-Boston-London.
• Lebedev, V. and Averbakh, I. (2006) Complexity of minimizing the Total flow time with interval data and minmax regret criterion. Discrete Applied Mathematics, 154, 2167-2177.
• Nowicki, E. and Smutnicki, C. (2006) Some aspects of scatter search in the flow-shop problem. European Journal of Operational Research, 169, 654-666.
• Pinedo, M.L. (2008) Scheduling-Theory, Algorithms and Systems. Springer.
• Savage, L.J. (1951) The theory of statistical decision. Journal of American Statist. Assoc., 46, 55-67.
• Volgenant, A. and Duin, C.W. (2010) Improved polynomial algorithms for robust bottleneck problems with interval data. Computers & Operations Research, 37(5), 909-915.
• Xu, J., Chiu, S.Y., Glover, F. (2001) Tabu Search and Evolutionary Scatter Search for 'Tree-Star' Network Problems, with Applications to Leased-Line Network Design. In: Telecommunications Optimization: Heuristic and Adaptive Techniques, Chapter 4. John Wiley & Sons.