Wyniki wyszukiwania - BazTech

1

Problem dystrybucji z terminami dostaw

Bożejko W., Walczyński M., Wodecki M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2008

|

z. 150

25-30

PL

W pracy przedstawiono algorytm oparty na metodzie przeszukiwania z tabu, rozwiązywania problemu dystrybucji z terminami dostaw. Jest on równoważny pewnemu jednomaszynowemu problemowi szeregowania, który w literaturze jest oznaczany przez 1|sij|ΣwiTi i należy do klasy problemów silnie NP-trudnych. Wykonano obliczenia na reprezentatywnej grupie danych, a otrzymane wyniki porównano z najlepszymi znanymi w literaturze.

EN

A tabu search algorithm is proposed in the paper to solve a distribution problem with due dates. It is equivalent to a single machine scheduling problem, which is described by 1|sij|ΣwiTi in the literature and it belongs to strongly NP-hard class. Calculations were done on representative group of test instances, obtained results were compared to the best known solutions from the literature.

2

Szeregowanie zadań z najwcześniejszymi i najpóźniejszymi terminami zakończenia

Bożejko W., Wodecki M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2006

|

z. 143

27-32

PL

W pracy przedstawiamy algorytm przybliżony oparły na metodzie przeszukiwania z tabu dla rozwiązywania problemu szeregowania na jednej maszynie zadań, z najwcześniejszymi i najpóźniejszymi terminami zakończenia. W procedurze przeglądania sąsiedztwa (ograniczonego przez eliminację "złych" rozwiązań) stosujemy, jako kryterium wyboru, górne ograniczenie wartości funkcji celu (rozwiązując problem "bez przestojów maszyny").

EN

In the paper we present an algorithm which is based on the tabu method to solving single machine scheduling problem with earliness and tardiness penalties. We apply an upper bound as the criterion in the neighborhood searching (solving "no idle" problem).

3

Jednomaszynowy problem szeregowania zadań z przezbrojeniami

Bożejko W., Wodecki M.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2006

|

z. 143

21-26

PL

W pracy przedstawiamy algorytm populacyjny rozwiązywania jednomaszynowego problemu szeregowania zadań z przezbrojeniami, w którym należy zminimalizować sumę kosztów opóźnień. W literaturze jest on oznaczany przez 1 | s[ij] | sigma w[i]T[i] należy do klasy problemów silnie NP-trudnych. Wykonaliśmy obliczenia na reprezentatywnej grupie danych testowych, a otrzymane wyniki porównujemy z najlepszymi znanymi w literaturze. Dla wielu przykładów uzyskaliśmy poprawę najlepszych rozwiązań.

EN

In the paper we propose a population-based algorithm for solving single machine scheduling problem with total tardiness criterion and sequence-dependent setup times. It is represented by 1 | s[ij] | sigma w[i]T[i] in literature and it belongs to the strongly NP-hard class. Calculations on the representative group of benchmark instances were done and results were compared with the best known from literature. Obtained solutions were better than benchmark ones in many instances.

4

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

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.