DISCRETE-CONTINUOUS SCHEDULING TO MINIMIZETHE MEAN FLOW TIME— COMPUTATIONAL EXPERIMENTS

Problems of scheduling nonpreemptable jobs which require simultaneously a machine from aset of parallel, identical machines and a continuous, renewable resource to minimize the meanflow time 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. Theproblem can be decomposed into two interrelated subproblems: (i) to sequence jobs onmachines, and (ii) to find an optimal (continuous) resource allocation among jobs alreadysequenced. For some special cases the problem can be solved in polynomial time. For thegeneral case we propose to use heuristic search methods defined on the space of feasiblesequences. Three metaheuristics: Tabu Search, Simulated Annealing and Genetic Algorithmhave been implemented and compared computationally. The computational experiment hasbeen carried out on a SGI PowerChallenge XL computer with 12 RISC R8000 processors.Some directions for further research have been pointed out.Pozna