Wyniki wyszukiwania - BazTech

1

Optimal resource allocation for single machine scheduling problems with time and resource dependent processing times.

Iwanowski D., Janiak A.

Systems Science

|

2002

|

Vol. 28, nr 2

85-94

EN

The paper is devoted to the single machine scheduling problems with time and resource dependent processing times. The following criteria are considered: the makespan and the total completion time subject to a given constraint on the total resource consumption and the total resource consumption criterion subject to a given constraint either on the makespan or on the total completion time, respectively. The problems are mostly NP-hard. The solution of such a kind of scheduling problem contains the permutation describing the optimal sequence of jobs and the optimal resource allocation vector. In general, there is no possibility to find the optimal sequence of jobs and the optimal resource allocation separately. Usually, the resource allocation depends on the sequence of jobs and the sequence depends on the resource allocation. Despite of that fact, in some particular applications the methods of an optimal resource allocation vector construction for a given arbitrary sequence of jobs may be very useful. For instance, such methods are necessary to construct some heuristic algorithms. Our interest was to find and describe these methods. We proved that they operate in polynomial time.

2

Minimalizacja globalnej ilości wykorzystanych zasobów dla jednomaszynowych problemów szeregowania zadań ze zmiennymi czasami wykonania

Iwanowski D., Janiak A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

z. 129

123-134

PL

W niniejszej pracy badane są jednomaszynowe problemy szeregowania zadań z czasami wykonania zależnymi od momentu rozpoczęcia wykonywania oraz ilości dostarczonego zasobu. Wykazano, że jeśli problem minimalizacji kryteriów czasowych takich jak długość uszeregowania oraz całkowity czas zakończenia wszystkich zadań przy ograniczeniu na całkowitą dostępną ilość zasobu jest problemem wielomianowym, to odpowiadający mu problem minimalizacji całkowitej ilości zasobu przy ograniczeniu na odpowiednie kryterium czasowe jest również problemem wielomianowym.

EN

The single machine job scheduling problems with time and resource dependent execution times have been examined in this paper. We proved, that if the problem of minimising the time criteria such as the makespan and the total completion time subject to a given constraint on the total resource consumption could be solved in polynomial time, then the corresponding problem of minimizing the total resource consumption subject to a given constraint on the value of the appropriate time criterion can be solved also in polynomial time.

3

Jednomaszynowe problemy szeregowania zadań ze zmiennymi czasami wykonania - podejście dwukryterialne

Iwanowski D., Janiak A.

Zeszyty Naukowe. Automatyka / Politechnika Śląska

|

2000

|

z. 129

111-121

PL

W pracy badane są jednomaszynowe problemy szeregowania zadań z czasami wykonania zależnymi od momentów rozpoczęcia oraz ilości dostarczonych zasobów. Wykazano, że jeśli problem minimalizacji kryteriów czasowych takich jak długość uszeregowani oraz całkowity czas zakończenia wszystkich zadań przy ograniczeniu na całkowitą dostępną ilość zasobów jest problemem wielomianowym, a także odpowiadający mu problem minimalizacji całkowitej ilości zasobu przy ograniczeniu na odpowiednie kryterium czasowe jest problemem wielomianowym, to możliwe jest skonstruowanie zbioru rozwiązań Pareto optymalnych (podejście dwukryterialne) również w czasie wielomianowym.

EN

The single machine job scheduling problems with time and resource dependent execution times are examined in this paper. We proved, that if the problem of minimizing criteria such as the makespan and total completion time with constrained value of total amount of resources available could be solved in polynomial time as well as corresponding version of this problem, where the total resource consumption is minimised subject to a given constraint on a time criterion, then the set of Pareto optimal solutions (bicriterional approach) can be easily constructed in polynomial time.