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.

• .

Bibliografia

• [1] ALDAEE B., LANDRAM F., Scheduling deteriorating Jobs on a single machine to minimise the maxi-mum processing times, International Journal of Systems Science, Vol. 27, No. 5, 1995, 507-510.
• [2] BACHMAN A., JANIAK A., Minimizing the makespan for the deteriorating jobs, Scientific Bulletins of Silesian Polytechnics, Automatics, Vol. 123, 1998, 23-29, (in Polish).
• [3] BACHMAN A., JANIAK A., Scheduling deteriorating jobs dependent on resources for the makespan minimization, [in:] B. Fleischmann et al. (eds.), Operations Research Proceedings 2000, Springer 2001,29-34.
• [4] GRAHAM R. L., LAWLER E. L., LENSTRA J. K., RINNOOY KAN A. H. G., Optimization and approxima. tion in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 1979 287-326.
• [5] IWANOWSKI D., JANIAK A., ROGALA A., Scheduling Jobs with Start Time and Resource Dependent Processing Times, [in:] K. Inderfurth et al. (eds.), Operations Research Proceedings 1999, Springer, 2000, 389-396.
• [6] MELNIKOV O., SHAFRANSKY Y., Parametric problem of scheduling theory, Kibernetika, 3, 1979, 53- 57, (in Russian).
• [7] MOSHEIOV G., V-Shaped Policies for Scheduling Deteriorating Jobs, Operations Research, Vol. 39/6, 1991,979-991.
• [8] MOSHEIOV G„ Scheduling jobs under simple linear deterioration, Computers and Operations Re¬search, Vol. 21/6, 1994, 653-659.
• [9] WAJS W., Polynomial algorithm for dynamic sequencing problem, The Archives of Automation and Telemechanics, 31/3, 1986, 209-213, (in Polish).