Szeregowanie zadań z przezbrojeniami i czasami wykonywania zadań zależnymi od zasobów - minimalizacja sumy ważonych czasów zakończenia wykonywania zadań

• Autorzy: Janiak A. , Krysiak T. , Lichtenstein M.

Warianty tytułu

EN

Scheduling jobs with resource dependent setup and processing times - total weighted completion time minimization

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

Abstrakty

PL

W pracy rozpatrzono dwa jednomaszynowe problemy szeregowania przy kryterium minimalizacji sumy ważonych czasów zakończenia wykonywania zadań oraz ograniczeniu na całkowitą ilość dostępnego zasobu. W pierwszym problemie czasy przezbrojeń są zależne od ilości przydzielonego zasobu, występuje tutaj także wymóg technologii grupowej. W drugim problemie czasy wykonywania zadań są zależne od zasobu, natomiast przezbrojenia są równe zero. Wykazano równoważność obu problemów dla malejącej funkcji liniowej opisującej zależność czasu przezbrojenia oraz czasu wykonywania od zasobu. Dla rozpatrywanych problemów wykazano szereg własności określających optymalne rozwiązania ich szczególnych przypadków oraz własności pomocnicze wykorzystane przy konstrukcji algorytmów heurystycznych rozwiązujących te problemy.

EN

The paper deals with two single machine scheduling problems considered for the sum of weighted completion times minimization. In the first problem, the setup times are resource-dependent and there is group technology restriction. In the second one the processing times are resource-dependent and the setup times are equal to zero. It is shown that both problems are equivalent if both the setup and processing times are decreasing resource dependent linear functions. We prove some properties for the considered problems, based on which some special cases of the considered problem can be solved optimally. These properties are also used to construct some heuristic algorithms solving the general cases of the problems under considerations. The efficiency of the heuristic algorithms is tested experimentally.

Słowa kluczowe

PL

szeregowanie zadań; problem jednomaszynowy

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

Twórcy

autor

Janiak A.

autor

Krysiak T.

autor

Lichtenstein M.

• Politechnika Wrocławska, Wrocław