Minimalizacja sumy opóźnień w jednomaszynowym problemie szeregowania zadań czasowo zależnych

• Autorzy: Janiak A. , Kozłowski J.

Warianty tytułu

EN

Minimizing the total tardiness for a single machine scheduling problem with deteriorating jobs

• Języki publikacji: PL

Abstrakty

PL

W pracy rozpatrywany jest jednomaszynowy problem szeregowania zadań z czasami wykonywania opisanymi liniową funkcją zależną od momentu rozpoczęcia ich wykonywania. Optymalizacji podlega suma opóźnień zadań. Badany problem jest NP-trudny nawet w przypadku stałych czasów wykonywania zadań, dlatego w celu jego rozwiązania skonstruowano szereg algorytmów przybliżonych, w których wykorzystano własności wykazane dla jego szczególnych przypadków. Jakość rozwiązań generowanych przez skonstruowane algorytmy została porównana eksperymentalnie.

EN

The paper deals with a single machine scheduling problem for the total tardiness minimization. The job processing time is given as start time dependent linear function, which contains two parts. The first part denotes a fixed processing time and the second part (characterized by a growth rate) describes the job processing time deterioration. Since the classical version of the latter problem is NP-hard, we constructed three approximation algorithms to solve its special cases. The algorithms were developed based on the problem properties, which were proved in the paper. In order to compare the quality of proposed algorithms, we performed a numerical experiment.

Słowa kluczowe

PL

szeregowanie zadań

EN

scheduling

• Wydawca: Wydawnictwa AGH
• Czasopismo: Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
• Rocznik: 2001
• Tom: T. 5, z. 1/2
• Strony: 259--268
• Opis fizyczny: Bibliogr. 7 poz., tab.

Twórcy

autor

Janiak A.

autor

Kozłowski J.

• Instytut Cybernetyki Technicznej, Politechnika Wrocławska

Bibliografia

• [1] Bachman A.: Jednomaszynowe problemy szeregowania zadań z czasami wykonywania zależnymi od ich momentu rozpoczęcia. Raport ICT Politechniki Wrocławskiej, PRE 78/98, Wrocław, 1998 (roz- prawa doktorska)
• [2] Bachman A., Janiak A., Kozłowski J.: Jednomaszynowy problem szeregowania zadań czasowo zależnych przy kryterium minimalizacji sumy opóźnień. Zesz. Nauk. Polit. Śl., Ser. Automatyka, z. 129,2000, 13-22
• [3] Du J., Leung J. Y.-T.: Minimizing total tardiness on one machine is NP-Hard. Mathematics of Operation Research, 15,1990,483-495
• [4] Graham R.L., Lawler E.L., Lenstra J.K., Rinnooy Kan A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 3,1979, 287-326
• [5] Janiak A.: Wybrane problemy i algorytmy szeregowania zadań i rozdziału zasobów. Warszawa, Akademicka Oficyna Wydawnicza PLJ 1999
• [6] MosheiovG.: V-shaped policies to schedule deteriorating jobs. Operations Research, 6/39, 1991, 979-991
• [7] Mosheiov G.: Schedulingjobs under simple linear deterioration. Computers and Operations Research, 6/21, 1994, 653-659