Jednomaszynowy problem szeregowania z potęgowymi funkcjami zmiany wartości zadań

• Autorzy: Bachman A. , Janiak A. , Kozik A. , Winczaszek M.

Warianty tytułu

EN

Single machine scheduling problem with exponentially dependent job values

• Konferencja: XIII Krajowa Konferencja Automatyzacji Procesów Dyskretnych
• Języki publikacji: PL

Abstrakty

PL

W niniejszej pracy rozpatrzono jednomaszynowy problem szeregowania, w którym wartości zadań zależą od momentów zakończenia ich wykonywania i są opisane malejącymi funkcjami potęgowymi. Rozwiązanie problemu polega na znalezieniu takiego uszeregowania, dla którego suma wartości zadań jest maksymalna. Problem sformułowany powyżej znajduje praktyczne zastosowanie np. w procesie odzysku surowców (np. części ze starych komputerów, samochodów), planowaniu sprzedaży, czy też magazynowaniu i transporcie produktów psujących się. Złożoność obliczeniowa rozpatrywanego problemu jest wciąż zagadnieniem otwartym, jednakże w pracy wykazano szereg własności określających optymalne rozwiązanie badanego problemu. Własności te zostały wykorzystane przy konstrukcji algorytmu opartego na metodzie podziału i ograniczeń. Dla skonstruowanego algorytmu przeprowadzono eksperyment obliczeniowy w celu określenia jego efektywności.

EN

The paper deals with a single machine scheduling problem, where job value is characterized by an exponential function dependent on job completion time. The objective is to find a sequence of jobs for which the sum of job values calculated at their completion times is maximized. The computational complexity status of the considered problem is still an open question, however it seams to be NP-hard. We proved some properties characterizing the optimal solution of the problem stated above. Based on these properties we constructed a branch and bound algorithm which quality was experimentally analyzed.

Słowa kluczowe

PL

problem jednomaszynowy; szeregowanie zadań

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 2002
• Tom: z. 134
• Strony: 13--22
• Opis fizyczny: Bibliogr. 3 poz.

Twórcy

autor

Bachman A.

• Politechnika Wrocławska, Wrocław

autor

Janiak A.

• Politechnika Wrocławska, Wrocław

autor

Kozik A.

• Politechnika Wrocławska, Wrocław

autor

Winczaszek M.

• Politechnika Wrocławska, Wrocław

Bibliografia

• 1. Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G.: Optimization and approximation in sequencing and scheduling: a survey, Annals of Discrete Mathematics, vol. 5,1979, s. 287-326.
• 2. Janiak A.: Wybrane problemy i algorytmy szeregowania zadań i rozdziału zasobów, Problemy Współczesnej Nauki, Teoria i Zastosowania - Informatyka, Akademicka Oficyna Wydawnicza PLJ, Warszawa 1999.
• 3. Voutsinas T. G., Pappis C. P.: Scheduling jobs with values exponentially deteriorating over time, Raport Techniczny Uniwersytetu w Pireusie, 2000