Minimizing the maximum completion time for the deteriorating jobs with ready times'

• Autorzy: Bachman A. , Janiak A.

Warianty tytułu

PL

Minimalizacja czasu zakończenia wykonywania zadań czasowo zależnych przy zadanych terminach dostępności

• Konferencja: XI Krajowa Konferencja Automatyzacji Dyskretnych Procesów Przemysłowych; Zakopane 24-27.09.1998
• Języki publikacji: EN

Abstrakty

EN

In this paper we consider the single machine problem with the maximum completion time criterion. Job processing time is described by a nondecreasing, linear function dependent on the job processing start time. Job ready time is also given for each job. We assume, that for each job, its processing time deterioration begins at its ready time. Each job is available for the time not smaller than its ready time. The job processing time consists of two parts: one is constant and the other one: variable, start time dependent. The variable part is characterised by the growth rate, which describes how fast the job processing time deteriorate. If the job begins exactly at its ready time, its processing time is equal only to its constant part. In this paper, for the problem mentioned above, we present the NP-completeness proof. We also present two heuristic algorithms. The first heuristic algorithm bases on the adjacent jobs interchanging and the second one on the extended Jackson's rule. In this paper we compare presented algorithms basing on the computational results.

PL

W pracy rozpatrywany jest jednomaszynowy problem minimalizacji czasu zakończenia wykonywania zadań czasowo zależnych przy zadanych terminach dostępności. Założono, że wydłużenie czasu wykonywania zadania, opisanego funkcją liniową, następuje od momentu jego dostępności. Zostało pokazane, że powyższy problem jest NP-zupełny. Przedstawiono dwa algorytmy rozwiązujące rozpatrywany problem w sposób przybliżony.

Słowa kluczowe

EN

single machine problem; problem NP-completeness

PL

szeregowanie zadań; maszyna pojedyńcza; problem NP-zupełny

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Zeszyty Naukowe. Automatyka / Politechnika Śląska
• Rocznik: 1998
• Tom: z. 123
• Strony: 33--44
• Opis fizyczny: Bibliogr. 8 poz.

Twórcy

autor

Bachman A.

autor

Janiak A.

• Politechnika Wrocławska