Wyniki wyszukiwania - BazTech

1

Single machine scheduling problem with job release dates consisting of a constant and a dynamic part

Janiak A., Słoniński P.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2001

|

T. 5, z. 1/2

289-297

EN

In this paper we present a solution of a scheduling problem with non-classical models of job release dates. (The release date can be interpreted as a preliminary process, which determines the moment at which the job can be processed on the single machine, e.g. the critical machine.) We assumed that the release date consists of a constant (not dependent on the resource) and a dynamic (differential) part. The state of the process that corresponds to the dynamic part is given by the differential equation, which determines the speed of the change of this process as a function of resource allocated. After the preliminary process (e.g. performed on parallel machines) is completed, the jobs are processed on a single critical machine. The processing time on the critical machine is constant and known a priori. In this paper we minimize the job completion time of a set of n jobs with the above models of release dates on a single machine. The global level of the resource that can be divided by the preliminary processes that determine the release dates of particular jobs is known. We are to find a permutation of jobs on the critical machine and resource allocation that minimizes the completion time of all jobs. It was shown that the above problem is NP-hard even for identical functions of job release models and identical constant parts of the dates; it is strongly NP-hard for different models of job release models and identical constant parts of the dates. Approximation algorithms for solving the considered problem are constructed. Their effectiveness was tested in experimental analysis.

PL

W pracy podano rozwiązanie problemu szeregowania zadań z nieklasycznymi modelami terminów dostępności. (Termin dostępności zadania może być interpretowany jako pewien wstępny proces, którego czas trwania determinuje moment gotowości zadania do właściwej obróbki na pojedynczej maszynie, np. maszynie krytycznej). Przyjęto, że model terminu dostępności zadań składa się z części stałej (której czas trwania nie zależy od ilości przydzielonego zasobu) i części dynamicznej (różniczkowej). Stan procesu odpowiadającego części dynamicznej jest opisany równaniem różniczkowym, które określa prędkość zmiany tego procesu w zależności od ilości przydzielonego zasobu ciągłego. Po zakończeniu procesu przygotowawczego (np. realizowanego na równoległych maszynach) zadania są wykonywane na pojedynczej maszynie krytycznej. Czas właściwej obróbki każdego zadania na maszynie krytycznej jest stały i znany a priori. W pracy minimalizuje się czas zakończenia wykonania zbioru n zadań o powyższych modelach terminów dostępności na pojedynczej maszynie. Znana jest przy tym ilość zasobu dostępna do rozdysponowania w każdej chwili pomiędzy procesy wyznaczające terminy dostępności poszczególnych zadań. Należy znaleźć takie uszeregowanie zadań na maszynie krytycznej oraz taki rozdział ograniczonego globalnie zasobu, aby czas zakończenia wykonania wszystkich zadań był minimalny. Wykazano, że powyższy problem jest NP-trudny nawet dla jednakowych funkcji modeli terminów dostępności i identycznej stałej części terminu dostępności, a silnie NP-trudny dla różnych funkcji i identycznej stałej części terminu dostępności. Skonstruowano algorytmy aproksymacyjne rozwiązywania rozpatrywanego problemu. Efektywność tych algorytmów sprawdzono na drodze eksperymentów obliczeniowych.

2

Minimizing the resource level in a scheduling problem with dynamic models of jobs on parallel machines

Janiak A., Słoniński P.

Automatyka / Akademia Górniczo-Hutnicza im. Stanisława Staszica w Krakowie

|

2001

|

T. 5, z. 1/2

283-288

EN

In this paper we assume a very general - dynamic (differential) - model of jobs. In such model the speed of changing the job state depends on the amount of resource allocated to this job. We present a solution of a problem of minimizing the resource level required to complete the processing of the set of n jobs with dynamic models. The resource level function R(t) is a sum of all resource allocated to the jobs at the moment t. The jobs are processed in parallel on m identical machines (processors) and are not preemptive. Additionally there is a constraint that the maximum job completion time does not exceed the given limit. The solution of this problem consists of finding an assignment of jobs to machines, a permutation of jobs on a particular machine and a resource allocation function, that minimizes the maximum level of resource R(t) required to complete the processing of a set of jobs on the parallel machines. The above problem is NP-hard. We show a few of its properties regarding the form of the solution. Additionally, for some classes of the job model functions, we pointed out the possibility of obtaining the analytical form of the function R(t).

PL

W niniejszej pracy przyjęto bardzo ogólny - dynamiczny (różniczkowy) - model zadania. W modelu tym prędkość zmiany stanu zadania w danej chwili zależy od ilości przydzielonego zasobu podzielnego w sposób ciągły. W pracy minimalizowano poziom zasobu koniecznego do wykonania zbioru n zadań o modelach dynamicznych. Funkcja R(t) poziomu zasobu jest sumą ilości zasobu przydzielonego do zadań w chwili t. Zadania są wykonywane na m równoległych identycznych maszynach (procesorach) i są niepodzielne. Ponadto znane jest ograniczenie na czas zakończenia wykonania wszystkich zadań. Rozwiązanie tego problemu polega na znalezieniu takiego przydziału zadań do procesorów, takiej permutacji zadań na poszczególnych procesorach oraz takiego przydziału zasobu, aby zminimalizować maksymalną wartość funkcji poziomu R(t) zasobu wymaganego do realizacji tych zadań w każdej chwili czasu t. Powyższy problem jest NP-trudny. Udowodniono szereg własności dotyczących postaci rozwiązania problemu. Ponadto, dla pewnych funkcji modeli zadań wskazano możliwość uzyskania wzorów analitycznych określających optymalną postać funkcji R(t).

3

Problem szeregowania zadań wykonywanych na jednej maszynie z dynamicznym modelem terminów ich dostępności

Janiak A., Słoniński P.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

z. 129

167-177

PL

W niniejszej pracy zaprezentowano rozwiązanie problemu minimalizacji czasu zakończenia wykonywania zbioru n zadań o dynamicznych modelach terminów dostępności na pojedynczej maszynie krytycznej. Dane jest ograniczenie na ilość zasobu dostępną do rozdysponowania w danej chwili. Wykazano szereg istotnych własności tego problemu, a na ich podstawie skonstruowano algorytm optymalnego rozdziału zasobu dla zadań w ustalonej permutacji oraz algorytm aproksymacyjny szeregowania zadań.

EN

The aim of this contribution is to present the solution of the problem of minimizing the time of processing a set of n jobs with dynamical (differential) models of job release dates on a single critical machine. The amount of resource available at each moment is known a priori. Many important properties of this problem have been proven. They are the base for construction of optimal resource allocation algorithm for jobs processed in a given permutation. There is also presented the approximation algorithm for the scheduling problem.

4

Minimalizacja sumarycznej ilości zużytego zasobu w problemie szeregowania zadań o dynamicznych modelach terminów dostępności

Janiak A., Słoniński P.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

z. 129

179-190

PL

W pracy zaprezentowano rozwiązanie problemu minimalizacji sumarycznej ilości zużytego zasobu przy dynamicznych (różniczkowych) modelach terminów dostępności zadań oraz przy ograniczeniu na czas zakończenia wykonywania wszystkich zadań. Wykazano szereg istotnych własności rozważanego problemu (między innymi dotyczących postaci funkcji rozdziału zasobu). Bazując na udowodnionych własnościach podano konstrukcję algorytmu szeregowania zadań na maszynie krytycznej oraz przydział zasobu do terminów dostępności zadań, który zapewnia zakończenie wykonywania zadań w ustalonym czasie minimalizując ilość zużytego na ten cel zasobu.

EN

The aim of this contribution is to present a solution of the problem of minimizing total amount of resource consumed in the resource allocation and scheduling problem with dynamic (differential) models of job release dates. There is also constraint set on the time of finishing processing of all the jobs in this problem. Many important properties of this problem have been proven (e.g. those concerning the character of the resource allocation function). The presented scheduling algorithm is based on the properties proven in this paper. There are also given some generalizations of the considered problem.