HEURISTIC PROCEDURES FOR ALLOCATING THE CONTINUOUS RESOURCE IN DISCRETE-CONTINUOUS SCHEDULING PROBLEMS

摘要

A problem of scheduling jobs on parallel, identical machines under an additional continuous resource to minimize the makespan is considered. Jobs are non-preemtable and independent, and all are available at the start of the process. The total amount of the continuous resource available at a time is limited, and the resource is a renewable one. Each job simultaneously requires for its processing a machine and an amount (unknown in advance) of the continuous resource. Processing rate of a job depends on the amount of the resource allotted to this job at a time. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the makespan. A heuristic approach to allocating the continuous resource is proposed. Four heuristic procedures are presented and discussed. A computational experiment is described, and the results produced by the heuristics are compared with optimal solutions. Some conclusions and directions for further research are given.