Jak szybko gasić pożar, czyli przypadek szeregowania zadań czasowozależnych

• Autorzy: Ocetkiewicz K. M. , Kubale M.

Warianty tytułu

EN

How to put out a fire fast: a case of time-dependent scheduling

• Języki publikacji: PL

Abstrakty

PL

Niniejszy artykuł poświęcony jest planowaniu pracy brygad strażackich walczących z pożarami lasu. Model matematyczny, który tutaj zastosowano, to szeregowanie zadań uwarunkowanych czasowo. Przedyskutowano złożoność problemu w przypadku zastosowania dwóch kryteriów optymalizacji: długości harmonogramu i średniego czasu przepływu. Pokazano, że w ogólności nie istnieją uszeregowania idealne, zapewniające minimalizację obu kryteriów jednocześnie.

EN

The article is devoted to scheduling jobs of fire fighting squads dealing with forest fire. Time-dependent scheduling is employed as a mathematical model. The complexity of two optimization criteria was discussed: the makespan and the total completion time. It is shown that, in general case, there are no ideal schedules that guarantee minimization of both of these goals simultaneously.

Słowa kluczowe

PL

szeregowanie zadań; uwarunkowanie czasowe; pożar

EN

computational complexity; fire fighting; time-dependent scheduling

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2011
• Tom: T. 15, z. 2
• Strony: 375--380
• Opis fizyczny: Bibliogr. 10 poz., rys.

Twórcy

autor

Ocetkiewicz K. M.

• Politechnika Gdańska, Katedra Algorytmów i Modelowania Systemów

autor

Kubale M.

• Politechnika Gdańska, Katedra Algorytmów i Modelowania Systemów

Bibliografia

• [1] Bachman A., Janiak A., Scheduling jobs with spedal type of start time dependent processing Times. Wrocław University of Technology, Report PRE 34/97, 1997.
• [2] Cheng T.C.E., Ding Q., Single machinę scheduling with deadlines and increasing rates of processing times. Acta Informatica 36, 2000, 673-692.
• [3] Dimopoulou M., Giannikos I., Towards an integrated framework for forest fire control. European J. Operational Research 152, 2004, 476^86.
• [4] Gawiejnowicz S., Pankowska L., Scheduling jobs with varying processing times. Infor. Process. Lett. 54, 1995, 175-176.
• [5] Kubale M., Ocetkiewicz K.M., Scheduling jobs to contain natural disaster: Models and comple-xity. Information Technologies 8, 2010, 333-338.
• [6] Mosheiov G., Scheduling jobs under simple linear deterioration. Comp. & Oper. Res. 21, 1994, 653-659.
• [7] Ocetkiewicz K.M., A FPTAS for minimizing total completion time in a single machinę time-de-pendent scheduling problem. European J. Operational Research 203, 2010, 316-320.
• [8] Ocetkiewicz K.M., Szeregowanie zadań uwarunkowanych czasowo. Politechnika Gdańska, Wydział ETI, Rozprawa doktorska /2011, 2011.
• [9] Pappis C.P., Rachaniotis N.P., Scheduling a single fire fighting resource with deteriorating fire suppression times and set-up times. Oper. Res. Int. J. 10, 2010, 27-2.
• [10] Rachaniotis N.P., Papis C.P., Scheduling fire tasks using the concept of "deteriorating jobs". Canadian J. Forest Research 36, 2006, 652-658.