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

• Autorzy: Iwanowski D. , Janiak A.
• Języki publikacji: EN

Abstrakty

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.

Słowa kluczowe

EN

single machine scheduling problems; time dependent processing time; resource dependent processing time; total resource consumption criterion; makespan constraint; total completion time constraint; NP-hard problems; optimal job sequence; optimal resource allocation vector; construction; heuristic algorithms; polynomial time methods

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Systems Science
• Rocznik: 2002
• Tom: Vol. 28, nr 2
• Strony: 85--94
• Opis fizyczny: Bibliogr. 9 poz.

Twórcy

autor

Iwanowski D.

• Institute of Engineering Cybernetics, Wrocław University of Technology, Janiszewskiego 11/17, 50-372 Wroclaw, Poland.

autor

Janiak A.

• Institute of Engineering Cybernetics, Wrocław University of Technology, Janiszewskiego 11/17, 50-372 Wroclaw, Poland.

• .