Pacific national university Main page Bulletin of Pacific national university

UDC 519.854.2

© O. E. Dolgova, V. V. Peresvetov, 2012

THE SINGLE-MACHINE SCHEDULING WITH MINIMIZATION OF THE TOTAL DELAY BY PARALLEL ANT COLONIES

The ant colony optimization metaheuristic algorithm with several parallel independent ant colonies has been worked out for solving the scheduling problem of processing a set of jobs on a single machine with the criterion of minimizing the total weighted delay. The effective complex local-search scheme with sequential application of stochastic methods has been proposed. The advantages of the parallel ant colonies’ search for the optimal solution are shown to consist in a higher rate of the convergence and stability of the time required for deriving optimal schedules. The results of calculations with the use of the parallel computing MPI technology are given.

Keywords: single-machine scheduling, minimizing the total weighted delay, parallel ant colonies.

References:

  1. Martin Josef Geiger. The single machine total weighted tardiness problem – is it (for metaheuristics) a solved problem? // The VIII Metaheuristics International Conference. Hamburg, 2009.
  2. An ant colony optimization approach for the single machine total tardiness problem / A. Bauer, B. Bullnheimer, R. F. Hartl, C. Strauss // In Proceedings of the 1999 Congress on Evolutionary Computation CEC99. Piscataway, NJ, 1999. Vol. 2.
  3. Lazarev A. A., Gafarov E. R. Teoriya raspisaniy. Minimizatsiya summarnogo zapazdyvaniya dlya odnogo pribora. M.: Vychislitel`nyy tsentr im. A. A. Dorodnitsyna RAN, 2006.
  4. Holthaus O., Rajendran C. A fast ant-colony algorithm for single-machine scheduling to minimize the sum of weighted tardiness of jobs // Journal of the Operational Research Society. 2005. No. 56.
  5. den Besten M., Stützle T., Dorigo M. Ant colony optimization for the total weighted tardiness problem // Lecture Notes in Computer Science, Springer-Verlag. Berlin, 2000. Vol. 1971.
  6. Merkle D., Middendorf M. An ant algorithm with a new pheromone evaluation rule for total tardiness problems // Lecture Notes in Computer Science, Springer-Verlag. Berlin, 2000. Vol. 1903.
  7. Dolgova O. E., Peresvetov V. V. Metod parallel`nykh murav`inykh koloniy v minimizatsii summarnogo vzveshennogo zapazdyvaniya dlya odnogo pribora: Preprint VTS DVO RAN. Habarovsk, 2011. No. 171.

Download Download article (315.6 Kb)

Сontents Сontents