OPTIMAL RESOURCE ALLOCATION FOR SINGLE MACHINE SCHEDULING PROBLEMS WITH TIME AND RESOURCE DEPENDENT PROCESSING TIMES

摘要

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.