Scheduling jobs to contain natural disaster model and complexity

• Autorzy: Kubale M. , Ocetkiewicz K.

Warianty tytułu

PL

Szeregowanie zadań w powstrzymywaniu katastrof naturalnych: model i złożoność

• Języki publikacji: EN

Abstrakty

EN

This paper is devoted to the problem of scheduling suppression units so that a natural disaster is dealt with as efficient as possible. The concept of deteriorating jobs is adopted, that is, the formal model of scheduling represents linearly increasing value loss as the disaster remains unsuppressed and increasing time for its suppression. More precisely, two different goals are considered: finding a suppression schedule of a minimal length, and finding a suppression schedule minimizing the total completion time. The former goal is advantageous to the suppression brigade, while the latter realizes the interest of the environment. We show that these two objectives are often in conflict. Then we review the state of the art concerning efficient solutions to the problem.

PL

Artykuł poświęcony jest problemowi szeregowania pracy oddziałów ratowniczych tak, aby jak najefektywniej zminimalizować skutki katastrofy naturalnej. Zastosowana jest koncepcja zadań uwarunkowanych czasowo, tj. formalny model szeregowania uwzględnia liniowy wzrost kosztów i czasu potrzebnego na zwalczenie skutków katastrofy. Rozważone są dwa różne kryteria: znalezienie harmonogramu o najmniejszej długości oraz wyznaczenie sekwencji działań minimalizującej całkowity czas wykonywania. Pierwsze kryterium reprezentuje interes oddziału, drugie zaś interes środowiska. Pokazujemy, że kryteria te często pozostają ze sobą w konflikcie. Przedstawiamy przegląd wiedzy na temat efektywnych rozwiązań przedstawionych problemów.

Słowa kluczowe

EN

scheduling jobs; natural disaster model

PL

szeregowanie zadań; powstrzymywanie katastrof naturalnych

• Wydawca: Wydział Elektroniki, Telekomunikacji i Informatyki Politechniki Gdańskiej
• Czasopismo: Zeszyty Naukowe Wydziału ETI Politechniki Gdańskiej. Technologie Informacyjne
• Rocznik: 2010
• Tom: T. 18
• Strony: 333--338
• Opis fizyczny: Bibliogr. 14 poz., rys.

Twórcy

autor

Kubale M.

autor

Ocetkiewicz K.

• Gdansk University of Technology Department of Algorithms and System Modelling

Bibliografia

• [1] Bachman A., Janiak A.: Scheduling jobs with special type of start time dependent processing times. Wroclaw University of Technology, Report PRE 34/97, 1997.
• [2] Bachman A., Janiak A., Kovalyov, M.Y.: Minimizing the total weighted completion time of deteriorating jobs. Information Processing Letters 81 (2), s. 81–84, 2002.
• [3] Cheng T.C.E., Ding Q.: Single machine scheduling with deadlines and increasing rates of processing times. Acta Informatica 36 (9–10), s. 673–692, 2000.
• [4] Gawiejnowicz, S., Pankowska, L.: Scheduling jobs with varying processing times. Information Processing Letters 54, s. 175–178, 1995.
• [5] Gawiejnowicz S., Lai T.-C., Chiang M.-H. Polynomially solvable cases of scheduling deteriorating jobs to minimize total completion time. Extended Abstracts of the 7-th Workshop on Project and Management Scheduling, s. 131–134, 2000.
• [6] Gawiejnowicz S., Kurc W., Pankowska L.: A greedy approach for a time-dependent scheduling problem. Lecture Notes in Computer Science 2328, s. 79–86, 2002.
• [7] Graham R.L., Lawler E.L., Lenstra J.K., Rinnoy Kan A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: A survey. Annals of Discrete Mathematics 5, s. 287–326, 1979.
• [8] Kubale M., Ocetkiewicz K.M.: A new optimal algorithm for a time-dependent scheduling problem. Control and Cybernetics, 38 (3), s. 713–721, 2009.
• [9] Mosheiov G. V-shaped policies for scheduling deteriorating jobs. Operation Research 39 (6),s. 979–991, 1991.
• [10] Mosheiov G.: Scheduling jobs under simple linear deterioration. Computers and Operations Research 21, 6, 653–659, 1994.
• [11] Ocetkiewicz K.M.: Porównanie heurystyk dla problemu szeregowania zadań czasowo-zależnych o wspólnym podstawowym czasie wykonywania (in Polish). Zeszyty Naukowe Wydziału ETI Politechniki Gdanskiej. Technologie Informacyjne 12, s. 145–152, 2007.
• [12] Ocetkiewicz K.M.: Algorytm branch-and-bound dla pewnego problemu szeregowania zadań uwarunkowanych czasowo (in Polish). Automatyka 13 (2), s. 521–529, 2009.
• [13] Ocetkiewicz K.M.: A FPTAS for minimizing total completion time in a single machine time-dependent scheduling problem. European Journal of Operational Research 203 (2), s. 316–320, 2010.
• [14] Rachaniotis N.P., Pappis C.P.: Scheduling fire-fighting tasks using the concept of „deteriorating jobs”. Canadian Journal of Forest Research 36, s. 652–658, 2006.