DISCRETE-CONTINUOUS SCHEDULING TO MINIMIZE THE MEAN FLOW TIME — COMPUTATIONAL EXPERIMENTS
Józefowska Joanna *), Mika Marek *), Różycki Rafał *), Waligóra Grzegorz *), Węglarz Jan *),**)
*)Institute of Computing Science, Poznań University of Technology, Piotrowo 3a,
60-965 Poznań, Poland, e-mail: office_ics@sol.put.poznan.pl
**)Poznań Supercomputing and Networking Centre, Wieniawskiego 17/19, Poznań, Poland
DOI: 10.12921/cmst.1997.03.01.25-37
OAI: oai:lib.psnc.pl:480
Abstract:
Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource to minimize the mean flow 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. 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. For some special cases the problem can be solved in polynomial time. For the general case 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. The computational experiment has been carried out on a SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out.
References:
Aarts E.H.L., and van Laarhoven P.J.M. (1987), Simulated Annealing: Theory and
Applications, Reidel, Dordrecht.
Davis L. (1985), „Applying adaptive algorithms to epistatic domains”, Proc. Internat.
Joint Conf. on Artificial Intelligence, 162-164.
Glover F. (1989), „Tabu Search – part 1″, ORSA J. Computing, 1, 190-206.
Glover F. (1990), „Tabu Search – part 2″, ORSA J. Computing, 2, 4-32.
Józefowska J., Dyskretno-ciągłe problemy szeregowania zadań”, rozprawa habilitacyjna.
Wydawnictwo Politechniki Poznańskiej, Poznań 1997.
Józefowska J., Waligóra G., and Węglarz J. (1996), „A Tabu Search algorithm for
some discrete-continuous scheduling problems”, in: V.J. Rayward-Smith, (ed.).
Modern Heuristics Search Methods, Wiley, 169-182.
Józefowska J., and Węglarz J. (1996), „Discrete-continuous scheduling problems –
Mean completion time results”, European Journal of Operational Research 94
(1996), pp.302-309.
Józefowska J., and Węglarz J. (1997), „On a methodology for discrete-continuous
scheduling”, European Journal of Operational Research.
Lawrence C., Zhou J.L., Tits A.L.: Users guide for C.FSQP Version 2.3 (Released
August 1995), available by e-mail: andre@eng.umd.edu.
Michalewicz Z. (1984), Genetic Algorithms + Data Structures = Evolution
Programs, Springer Verlag.
Osman I.H., Potts C.N. (1989), „Simulated annealing for permutation flow shop
scheduling problem”, Omega 16, 7, 551-557.
Węglarz J. (1982), Modelling and control of dynamic resource allocation project
scheduling systems, in: Tzafestas S.G. (ed.) Optimization and Control of
Dynamic Operational Research Models. North Holland, 105-140.
Problems of scheduling nonpreemptable jobs which require simultaneously a machine from a set of parallel, identical machines and a continuous, renewable resource to minimize the mean flow 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. 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. For some special cases the problem can be solved in polynomial time. For the general case 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. The computational experiment has been carried out on a SGI PowerChallenge XL computer with 12 RISC R8000 processors. Some directions for further research have been pointed out.
Aarts E.H.L., and van Laarhoven P.J.M. (1987), Simulated Annealing: Theory and
Applications, Reidel, Dordrecht.
Davis L. (1985), „Applying adaptive algorithms to epistatic domains”, Proc. Internat.
Joint Conf. on Artificial Intelligence, 162-164.
Glover F. (1989), „Tabu Search – part 1″, ORSA J. Computing, 1, 190-206.
Glover F. (1990), „Tabu Search – part 2″, ORSA J. Computing, 2, 4-32.
Józefowska J., Dyskretno-ciągłe problemy szeregowania zadań”, rozprawa habilitacyjna.
Wydawnictwo Politechniki Poznańskiej, Poznań 1997.
Józefowska J., Waligóra G., and Węglarz J. (1996), „A Tabu Search algorithm for
some discrete-continuous scheduling problems”, in: V.J. Rayward-Smith, (ed.).
Modern Heuristics Search Methods, Wiley, 169-182.
Józefowska J., and Węglarz J. (1996), „Discrete-continuous scheduling problems –
Mean completion time results”, European Journal of Operational Research 94
(1996), pp.302-309.
Józefowska J., and Węglarz J. (1997), „On a methodology for discrete-continuous
scheduling”, European Journal of Operational Research.
Lawrence C., Zhou J.L., Tits A.L.: Users guide for C.FSQP Version 2.3 (Released
August 1995), available by e-mail: andre@eng.umd.edu.
Michalewicz Z. (1984), Genetic Algorithms + Data Structures = Evolution
Programs, Springer Verlag.
Osman I.H., Potts C.N. (1989), „Simulated annealing for permutation flow shop
scheduling problem”, Omega 16, 7, 551-557.
Węglarz J. (1982), Modelling and control of dynamic resource allocation project
scheduling systems, in: Tzafestas S.G. (ed.) Optimization and Control of
Dynamic Operational Research Models. North Holland, 105-140.
