Local search metaheuristics for discrete continuous scheduling problems

Local search metaheuristics for discrete continuous scheduling problems

0.00 Avg rating0 Votes
Article ID: iaor19992327
Country: Netherlands
Volume: 107
Issue: 2
Start Page Number: 354
End Page Number: 370
Publication Date: Jun 1998
Journal: European Journal of Operational Research
Authors: , , , ,
Keywords: heuristics, optimization: simulated annealing
Abstract:

Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource are considered. For each job there are known: its processing speed as a continuous, concave function of a continuous resource allotted at a time and its processing demand. The optimization criterion is the schedule length. The problem can be decomposed into two interrelated subproblems: (i) to sequence jobs on machines, and (ii) to find an optimal (continuous) resource allocation among jobs already sequenced. Problem (ii) can be formulated as a convex programming problem with linear constraints and solved using proper solvers. Thus, the problem remains to generate a set of all feasible sequences of jobs on machines (this guarantees finding an optimal schedule in the general case). However, the cardinality of this set grows exponentially with the number of jobs. Thus, we propose to use heuristic search methods defined on the space of feasible sequences. Three metaheuristics, tabu search, simulated annealing and genetic algorithm, have been implemented and compared computationally with a random sampling technique. The computational experiment has been carried out on an SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out.

Reviews

Required fields are marked *. Your email address will not be published.