Wyniki wyszukiwania - BazTech

Ograniczanie wyników

4 Zeszyty Naukowe. Automatyka / Politechnika Śląska

4 1998

Powiadomienia systemowe

Sesja wygasła!
Sesja wygasła!

Znaleziono wyników: 4

Liczba wyników na stronie

Wyniki wyszukiwania

Wyszukiwano:
w słowach kluczowych: maszyna pojedyńcza

Sortuj według:

Ogranicz wyniki do:

Szeregowanie zadań z przezbrojeniami przy ograniczeniach zasobowych

Chudzik K., Janiak A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

1998

z. 123

85-96

Praca poświęcona jest jednomaszynowym problemom szeregowania zadań z przezbrojeniami. Zaprezentowano złożoność obliczeniową i przegląd rezultatów dla klasycznych problemów. Wprowadzono nowe modele, gdzie czas przezbrojenia jest funkcją przydzielonych zasobów. Wykazano ich złożoność obliczeniową.

The paper deals with the single machine scheduling problems with setups. Complexity and results for the classic problems are presented. New models with setups that are some functions of the alloted are introduced. Their computational complexity is considered.

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

Bachman A., Janiak A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

1998

z. 123

33-44

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.

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.

Minimalizacja maksymalnej nieterminowości dla zadań czasowo zależnych

Bachman A., Janiak A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

1998

z. 123

23-31

W pracy rozpatrywano jednomaszynowy problem szeregowania zadań czasowo zależnych przy kryterium minimalizacji maksymalnej nieterminowości wykonania. Założono, że czas wykonywania zadania, dany w postaci liniowej, niemalejącej funkcji terminu rozpoczęcia wykonywania składa się z dwóch części: stałej i zmiennej. Stała część, niezależna od terminu rozpoczęcia, określa pewną minimalną długość czasu wykonywania zadania, wynikającą z uwarunkowań technologicznych. Natomiast zmienna część, charakteryzowana przez czynnik wzrostu, opisuje wpływ terminu rozpoczęcia wykonywania na wydłużenie zadania. Pokazano, że przy tak scharakteryzowanym modelu jednomaszynowy problem szeregowania zadań przy kryterium minimalizacji maksymalnej nieterminowości jest NP-zupełny.

The paper deals with the single machine scheduling problem, where the job processing time is given as a linear, nondecreasing function dependent on the processing start time. The function describing the job processing time consists of two parts, where one is constant and describes the minimal time required to complete the job if its starting moment is equal to zero. The second part, characterized by the growth rate, describes how fast the job processing time deteriorate. We showed that such a described problem for the maximum lateness criterion is NP-complete by reducing to it NP-complete Partition Problem.

Algorytm tabu search dla wybranych problemów szeregowania zadań na pojedynczej maszynie z przezbrojeniami

Chudzik K., Janiak A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

1998

z. 123

97-109

Artykuł poświęcony jest szeregowaniu zadań na pojedynczej maszynie z przezbrojeniami sekwencyjnie zależnymi. Rozpatrywane są trzy kryteria : 1) czas zakończenia wykonywania wszystkich zadań, 2) maksymalna nieterminowość, 3) suma ważonych czasów zakończenia wykonywania zadań. Prezentowane problemy są NP-trudne. Do ich rozwiązania użyto algorytmu typu tabu search.

The paper is devoted to single machine scheduling problems with sequence dependent setup times. The following criterion functions are considered: 1) maximum completion time (makespan), 2) maximum lateness, and 3) weighted sum of completion times. Presented problems are NP-hard. A tabu search algorithms was to solve these problems.