On a machine scheduling problem solving.

Emil Yu. Orekhov, Yuri V. Orekhov: On a machine scheduling problem solving CSIT 2000 : 33-37


In present paper we consider the problem of scheduling n jobs between m unrelated parallel machines minimizing the maximum completion time (R||Cmax according to three-field representation described in [1]). Using algorithm that is based on branch-and-bound method and always delivers an optimum solution is appropriate when solving small instances of R||Cmax (up to 8 machines and 25 jobs). For larger problems it is advisable to use the stochastic algorithms. Defining a set that contains all the optimum solutions and therefore excluding from further consideration all certainly non-optimum solutions can significantly increase their efficiency.

Copyright © 2000 by the Institute for Contemporary Education "JurInfoR-MSU". Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the CSIT copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Institute for Contemporary Education JMSUICE. To copy otherwise, or to republish, requires a fee and/or special permission from the JMSUICE.

Printed Edition

Heinz Schweppe and Yuri S. Kabalnov (Eds.): CSIT'2000, Proceedings of 2nd International Workshop on Computer Science and Information Technologies, September 18-23, 2000, Ufa, Russia. USATU Publishers & JurInfoR-MSU Publishing 2000, ISBN 5-86911-312-1

Electronic Edition