A performance analysis of tabu search for discrete-continuous scheduling problems
[ 1 ] Instytut Informatyki (II), Wydział Informatyki i Zarządzania, Politechnika Poznańska | [ P ] employee
2004
chapter in monograph
english
- discrete-continuous scheduling problems
- makespan
- mean flow time
- maximum lateness
- tabu search
- tabu navigation method
- cancellation sequence method
- reverse elimination method
EN Problems of scheduling jobs on parallel, identical machines under an additional continuous resource are 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. The processing rate of a job depends on the amount of the resource allotted to this job at a time. Three scheduling criteria are considered: the makespan, the mean flow time, and the maximum lateness. The problem is to find a sequence of jobs on machines and, simultaneously, a continuous resource allocation that minimize the given criterion. A tabu search metaheuristic is presented to solve the problem. A computational analysis of the tabu search algorithm for the considered discrete-continuous scheduling problems is presented and discussed. Three different tabu list management methods are tested: the tabu navigation method, the cancellation sequence method, and the reverse elimination method.
385 - 404