Szeregowanie zadań o zmiennych wartościach z różnymi terminami dostępności – algorytmy rozwiązania

• Autorzy: Janiak A. , Kołodka P. , Krysiak T.

Warianty tytułu

EN

Scheduling jobs with changeable job values and different release dates – solution algorithms

• Języki publikacji: PL

Abstrakty

PL

Praca dotyczy problemu szeregowania zadań o zmiennych wartościach i niezerowych terminach dostępności na pojedynczej maszynie. Analizowano potęgowy model wartości zadań, a jako kryterium – maksymalizację sumy wartości wszystkich zadań. Problem powyższy jest co najmniej NP-trudny. Do jego rozwiązania skonstruowano algorytm dokładny typu podziału i ograniczeń oraz szereg algorytmów heurystycznych typu konstrukcyjnego, a także jeden typu popraw. Efektywność skonstruowanych algorytmów przebadano eksperymentalnie.

EN

The paper deals with a problem of scheduling jobs with changeable job values and non-zero release dates on a single machine. A power model of job values and the criterion of maximization of the total job values are analyzed. The above problem is at least NP-hard. Thus, a branch and bound exact algorithm and some heuristic algorithms (constructive and improving type) have been developed. Their efficiency have been examined experimentally.

Słowa kluczowe

PL

szeregowanie zadań; zmienne wartości; metoda podziału i ograniczeń; algorytm heurystyczny

EN

scheduling jobs; changeable job values; branch and bound; heuristic algorithm

• Wydawca: Wydawnictwo SIGMA-NOT
• Czasopismo: Przegląd Elektrotechniczny
• Rocznik: 2010
• Tom: R. 86, nr 9
• Strony: 91--96
• Opis fizyczny: Bibliogr. 11 poz., tab.

Twórcy

autor

Janiak A.

autor

Kołodka P.

autor

Krysiak T.

• Instytut Informatyki, Automatyki i Robotyki, Politechnika Wrocławska, ul. Janiszewskiego 11/17, 50-372 Wrocław,

Bibliografia

• [1] Janiak A., Krysiak T., Pappis C.P., Voutsinas T.G.: A scheduling problem with job values given as a power function of their completion times, European Journal of Operational Research, 193 (2009), 836–848
• [2] Bachman A., Janiak A., Krysiak T.: Jednomaszynowy problem szeregowania zadań o zmiennych wartościach, XIII Krajowa Konferencja Automatyzacji Procesow Dyskretnych, Zakopane, 11-14.09.2002, Gliwice, Wydaw. PŚl. (2002), 33-42
• [3] Janiak A., Krysiak T., Pappis C.P.: Parallel processor scheduling problems with exponential models of job values, W: Scheduling in computer and manufacturing systems, Janiak A. (Red.), Warszawa, WKŁ (2006), 115-134
• [4] Voutsinas T.G., Pappis C.P.: Scheduling jobs with values exponentially deteriorating over time, International Journal of Production Economics, 79 (2002), 163-169
• [5] Janiak A., Kasperski A., Krysiak T.: Scheduling jobs with a stepwise function of change of their values, W: Operations research. Proceedings 2003. Selected papers of the International Conference on Operations Research (OR 2003), Heidelberg, 3-5.09.2003, Ahr D. i in. (Red.), Berlin i in., Springer (2004), 363-370
• [6] Janiak A., Krysiak T.: Single processor scheduling with job values depending on their completion times, Journal of Scheduling, 10 (2007), 129-138
• [7] Janiak A., Krysiak T.: Scheduling problems with stepwise and piecewise linear models of job values, W: Scheduling in computer and manufacturing systems, Janiak A. (Red.), Warszawa, WKŁ (2006), 135-152
• [8] Raut S., Gupta J.N., Swami S.: Single machine scheduling with time deteriorating job values, Journal of the Operational Research Society, 59 (2008), 105–118
• [9] Raut S., Swami S., Gupta J.N.: Scheduling a capacitated single machine with time deteriorating job values, International Journal of Production Economics, 114 (2008), 769–780
• [10] Kwiatkowski J., Pawlik M.: Budowa struktur gridowych wspołdziałających komputerow i agregacji zasobow w strukturach organizacyjnych, Przegląd Elektrotechniczny, 9 (2009), 221-225
• [11] Powróznik P.: Elastyczny model szeregowania zadań w systemach pomiarowo — sterujących z wykorzystaniem algorytmu ewolucyjnego, Przegląd Elektrotechniczny, 2 (2009), 79-82