Wyniki wyszukiwania - BazTech

Ograniczanie wyników

2 Zeszyty Naukowe. Automatyka / Politechnika Śląska

2 2002

Znaleziono wyników: 2

Liczba wyników na stronie

Wyniki wyszukiwania

Sortuj według:

Ogranicz wyniki do:

Przybliżone algorytmy rozwiązywania jednomaszynowego problemu szeregowania zadań o zmiennych wartościach

Bachman A., Janiak A., Kozik A., Winczaszek M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2002

z. 134

23-32

W mniejszej pracy rozpatrzono jednomaszynowy problem szeregowania zadań przy kryterium maksymalizacji sumy wartości zadań. Wartość zadania jest opisana malejącą funkcją potęgową zależną od jego czasu zakończenia wykonywania. Dla badanego problemu skonstruowano i porównano eksperymentalnie szereg algorytmów heurystycznych typu konstrukcyjnego i typu "popraw".

The paper deals with a single machine scheduling problem where the sum of job values should be maximized. A job value is given as a exponentially decreasing function dependent on its completion time. We experimentally compared some heuristic algorithms constructed to solve the problem under consideration.

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

Bachman A., Janiak A., Kozik A., Winczaszek M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

2002

z. 134

13-22

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.

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.