PL
 |
EN
Preferencje help
Polish version English version Język
Widoczny [Schowaj] Abstrakt
Liczba wyników

Znaleziono wyników: 10

Liczba wyników na stronie
first rewind previous Strona / 1 next fast forward last
Wyniki wyszukiwania
help Sortuj według:

help Ogranicz wyniki do:
first rewind previous Strona / 1 next fast forward last
1
Przybliżone algorytmy rozwiązywania jednomaszynowego problemu szeregowania zadań o zmiennych wartościach
Bachman A., Janiak A., Kozik A., Winczaszek M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
23-32
PL
W mniejszej pracy rozpatrzono jednomaszynowy problem szeregowania zadań przy kryterium maksymalizacji sumy wartości zadań. Wartość zadania jest opisana malejącą funkcją potęgową zależną od jego czasu zakończenia wykonywania. Dla badanego problemu skonstruowano i porównano eksperymentalnie szereg algorytmów heurystycznych typu konstrukcyjnego i typu "popraw".
EN
The paper deals with a single machine scheduling problem where the sum of job values should be maximized. A job value is given as a exponentially decreasing function dependent on its completion time. We experimentally compared some heuristic algorithms constructed to solve the problem under consideration.
2
Jednomaszynowy problem szeregowania zadań o zmiennych wartościach
Bachman A., Janiak A., Krysiak T.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
33-42
PL
W pracy rozpatrzono jednomaszynowy problem szeregowania, w którym wartości zadań są opisane potęgową funkcją zależną od czasów zakończenia ich wykonywania. Rozpatrzono kryterium maksymalizacji sumy wartości zadań. Analizowany problem został przeformułowany w taki sposób, że zamiast maksymalizacji sumy wartości zadań, optymalizowanym kryterium jest minimalizacja sumy strat ich wartości. Określono złożoność obliczeniową ogólnej wersji problemu wykorzystując transformację z Problemu Podziału. Dla szczególnych przypadków badanego problemu wykazano szereg własności określających optymalne rozwiązanie.
EN
The paper deals with a single machine scheduling problem where job values are characterized by an exponential function dependent on the completion time of job execution. Maximization of the total values is considered as an optimization criterion. However, to simplify the considerations, we reformulate the problem so that the total lost of job values should be minimized. We prove that the general version of the problem stated above is NT-hard. The proof is done from the well known Partition Problem. We construct some optimal algorithms which solve special cases of the general problem in polynomial time.
3
Jednomaszynowy problem szeregowania z potęgowymi funkcjami zmiany wartości zadań
Bachman A., Janiak A., Kozik A., Winczaszek M.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2002
|
z. 134
13-22
PL
W niniejszej pracy rozpatrzono jednomaszynowy problem szeregowania, w którym wartości zadań zależą od momentów zakończenia ich wykonywania i są opisane malejącymi funkcjami potęgowymi. Rozwiązanie problemu polega na znalezieniu takiego uszeregowania, dla którego suma wartości zadań jest maksymalna. Problem sformułowany powyżej znajduje praktyczne zastosowanie np. w procesie odzysku surowców (np. części ze starych komputerów, samochodów), planowaniu sprzedaży, czy też magazynowaniu i transporcie produktów psujących się. Złożoność obliczeniowa rozpatrywanego problemu jest wciąż zagadnieniem otwartym, jednakże w pracy wykazano szereg własności określających optymalne rozwiązanie badanego problemu. Własności te zostały wykorzystane przy konstrukcji algorytmu opartego na metodzie podziału i ograniczeń. Dla skonstruowanego algorytmu przeprowadzono eksperyment obliczeniowy w celu określenia jego efektywności.
EN
The paper deals with a single machine scheduling problem, where job value is characterized by an exponential function dependent on job completion time. The objective is to find a sequence of jobs for which the sum of job values calculated at their completion times is maximized. The computational complexity status of the considered problem is still an open question, however it seams to be NP-hard. We proved some properties characterizing the optimal solution of the problem stated above. Based on these properties we constructed a branch and bound algorithm which quality was experimentally analyzed.
4
Content available remote "Learning effect" considerations in single machine scheduling problems
Bachman A., Janiak A., Kozłowski J.
Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie
|
2001
|
T. 5, z. 1/2
65-70
EN
The paper deals with single machine scheduling problems, in which job processing time is given as a non-increasing function dependent on the number of previuosly executed jobs. Such a dependency describes a "learning effect", which frequently occurs in manufacturing processes. We presented a detailed literature survey of scheduling problems, in which this phenomenon has been investigated. We solved optimally five problems with "learning effect" considerations for the following criteria: the makespan, the total completion time and the total weighted completion time.
PL
Niniejsza praca jest poświęcona zjawisku, które można określić mianem "efektu uczenia", a które występuje bardzo często w problemach harmonogramowania procesów produkcyjnych. W pracy scharakteryzowano modele opisujące badane zjawisko. Zebrano rezultaty związane z jednomaszynowymi problemami szeregowania, w których czas wykonywania zadania opisuje "efekt uczenia", tzn. jest dany jako nierosnąca funkcja zależna od liczby zadań wykonanych uprzednio. Rozwiązano optymalnie pięć problemów szeregowania przy rozpatrywanych modelach czasu wykonywania zadania dla następujących kryteriów: minimalizacja długości uszeregowania, minimalizacja sumy czasów zakończenia wykonania zadań oraz minimalizacja sumy ważonych czasów zakończenia wykonania zadań.
5
Jednomaszynowy problem szeregowania zadań czasowo zależnych przy kryterium minimalizacji sumy opóźnień
Bachman A., Janiak A., Kozłowski J.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
13-22
PL
W pracy rozpatrywano jednomaszynowy problem szeregowania zadań przy kryterium minimalizacji sumy opóźnień. Założono, że czasy wykonywania zadań są liniowo zależne od momentów rozpoczęcia ich wykonywania. Analizowano problemy z jednym wspólnym, dwoma oraz wieloma różnymi pożądanymi terminami zakończenia wykonania zadań. Dla szczególnych przypadków rozpatrywanego problemu skonstruowano optymalne algorytmy wielomianowe.
EN
In the paper we consider a single machine scheduling problem of minimizing the total tardiness. The job processing times are given as start time dependent linear functions. We present some optimal solutions for the special cases of the problem under consideration.
6
Jednomaszynowy problem szeregowania zadań czasowo i zasobowo zależnych przy kryterium minimalizacji czasu zakończenia wykonania zadań
Bachman A., Janiak A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
2000
|
z. 129
23-32
PL
W niniejszej pracy wykazano NP-zupełność jednomaszynowego problemu szeregowania zadań z czasami wykonywania zależnymi zarówno od momentu rozpoczęcia wykonywania, jak również od ilości przydzielonego zasobu przy kryterium minimalizacji czasu zakończenia wykonania zadań.
EN
The paper deals with a single machine scheduling problem, in which the job processing times are start time and resource dependent. We prove that this problem is NP-complete for the makespan minimization.
7
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.
8
Minimalizacja maksymalnej nieterminowości dla zadań czasowo zależnych
Bachman A., Janiak A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 123
23-31
PL
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.
EN
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.
9
Analiza jednomaszynowych problemów szeregowania zadań z czasowo zależnymi czasami wykonywania
Bachman A., Janiak A.
Zeszyty Naukowe. Automatyka / Politechnika Śląska
|
1998
|
z. 123
11-22
PL
W pracy dokonano przeglądu literaturowego jednomaszynowych problemów szeregowania zadań, których czasy wykonywania są pewnymi funkcjami zależnymi od momentu rozpoczęcia ich wykonywania. Autorzy dokonali porównania różnych modeli opisujących rozpatrywaną zależność czasu wykonywania zadania ze względu na stosowane kryteria.
EN
In the paper we analysed the single machine scheduling problems with start time dependent processing times. We presented the complete state of art in this area containing thirty three articles from last twenty years. The notation of the presented models have been unified. We described also the techniques used to solve considered problem with some remarkable results.
10
Szeregowanie zadań na pojedynczej maszynie z przezbrojeniami i terminami dostępności zadań - algorytm tabu search
Bachman A., Chudzik K., Janiak A.
Mechanika / Akademia Górniczo-Hutnicza im. St. Staszica
|
1998
|
T. 17, z. 2
205-214
PL
Artykuł poświęcony jest szeregowaniu zadań z przezbrojeniami na jednej maszynie, gdzie zadania mają określone terminy dostępności. Rozpatrywane kryterium to czas ukończenia wykonywania wszystkich zadań. Problem jest sformułowany następująco. Danych jest n zadań, gdzie każde posiada określony termin dostępności i czas wykonywania na maszynie. Przerywanie wykonywania zadań jest niedozwolone. Zbiór zadań podzielony jest na podzbiory, zwane rodzinami. Pomiędzy dwoma kolejnymi zadaniami wymagane jest przezbrojenie, jeżeli zadania należą do różnych rodzin. Także przed pierwszym zadaniem wykonywanym na maszynie wymagane jest przezbrojenie przygotowawcze. Przezbrojenie zabiera określony czas i podczas jego trwania następuje przygotowanie maszyny, np.: wymiana narzędzi w centrum obróbkowym. Czas przezbrojenia zależy od rodziny zadania, które zostało właśnie ukończone, i od rodziny zadania, które ma być wykonywane. Czas ten jest więc sekwencyjnie zależny. Celem optymalizacji jest znalezienie kolejności wykonywania zadań, która minimalizuje kryterium czasu ukończenia wykonywania wszystkich zadań. Problem jest silnie NP-trudny. Do jego rozwiązania użyto klasycznego algorytmu typu tabu search. Praca zawiera: precyzyjne sformułowanie problemu, krótki opis algorytmu, opis eksperymentu numerycznego, rezultaty eksperymentu i wnioski.
EN
The paper deals with single machinę task scheduling problem with setups and ready times. The criterion is the maximum task completion time. The problem is formulated as follows. There are n tasks. For each task its ready and processing times are given. Task premption is not allowed. The set of tasks is partitioned into task subsets, called families each task belongs to one family only). An initial setup time is required for first performed task. The setup time depends only on family which task belongs to. A setup time is required also between two consecutive tasks when these tasks belong to different families. In practice, it is an idle time when the machine is prepared for processing task from other family than just finished. A setup time is not required between two tasks which belong to the same family. The setup time is sequencially dependent. The problem is to find such a job processing order that the maximum job completion time is minimised. The problem is strongly NP-hard. Some algorithm of tabu search type was constructed to solve the problem under consideration. The results of some computation experiment together with some conclusions are also given.
first rewind previous Strona / 1 next fast forward last
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.