Tabu list management methods for a discrete–continuous scheduling problem

A problem of scheduling jobs on parallel, identical machines under an additional continuous resource to minimize the makespan is considered. Jobs are non-preemptable 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 minimizes the makespan. The tabu search metaheuristic is presented to attack the problem. Three different tabu list management methods: the tabu navigation method, the cancellation sequence method and the reverse elimination method are discussed and examined. A computational experiment is described and the results obtained for the methods tested are compared to optimal solutions. A few conclusions and final remarks are presented.