PROBABILISTIC TABU SEARCH FOR MAKESPAN MINIMIZATION DISCRETE-CONTINUOUS SCHEDULING

摘要

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. The tabu search metaheuristic is presented to attack the problem. Probabilistic implementations of tabu search are discussed and examined. A computational experiment is described, and the results obtained for the probabilistic version of tabu search are compared to optimal solutions. A few conclusions and final remarks are presented.