On scheduling with technology based machines grouping

A. V. Eremeev ; Ju. V. Kovalenko

Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 5, pp. 54-79.

Résumé

A problem of multi-product scheduling is considered. Each product can be produced by a family of alternative multi-machine technologies which require more than one machine at the same time. The problem is studied in two versions: with and without preemptions of technologies processing. We formulate mixed integer linear programming models for both versions. Two genetic algorithms are proposed and experimentally tested. The first one is based on a uniform crossover and the second one uses a new optimal recombination operator. Convergence of the proposed algorithms is investigated. Computational complexity of the problem is analyzed. Ill. 1, tab. 5, bibliogr. 28.

Détail

Keywords: scheduling, setup time, technology, integer linear programming, genetic algorithm.

Bibliographie

[1] Borisovskii P. A., “Geneticheskii algoritm dlya odnoi zadachi sostavleniya proizvodstvennogo raspisaniya s perenaladkami”, Tr. XIV Baikalskoi mezhdunar. shkoly-seminara “Metody optimizatsii i ikh prilozheniya”, v. 4, ISEM SO RAN, Irkutsk, 2008, 166–173

[2] Gmurman V. E., Teoriya veroyatnostei i matematicheskaya statistika, Uch. pos., Vysshee obrazovanie, M., 2006, 479 pp.

[3] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

[4] Ilev V. P., “Otsenki pogreshnosti priblizhënnogo algoritma dlya zadachi o raskraske grafa”, Tr. XIII Baikalskoi mezhdunar. shkoly-seminara "Metody optimizatsii i ikh prilozheniya, v. 1, ISEM SO RAN, Irkutsk, 2005, 491–495

[5] Kitaev A., Shen A., Vyalyi M., Klassicheskie i kvantovye vychisleniya, MTsNMO, CheRo, M., 1999, 192 pp.

[6] Kovalenko Yu. V., Model s nepreryvnym predstavleniem vremeni dlya zadachi sostavleniya raspisanii mnogoproduktovogo proizvodstva, Preprint, Cornell University, Cornell, 2011, 8 pp., arXiv: 1105.2437[math.OC]

[7] Rutkovskaya D., Pilinskii M., Rutkovskii L., Neironnye seti, geneticheskie algoritmy i nechëtkie sistemy, Goryachaya liniya–Telekom, M., 2006, 452 pp.

[8] Tanaev V. S., Kovalev M. Ya., Shafranskii Ya. M., Teoriya raspisanii. Gruppovye tekhnologii, In-t tekhn. kibernetiki NAN Belarusi, Minsk, 1998, 290 pp.

[9] Khachiyan L. G., “Polinomialnye algoritmy v lineinom programmirovanii”, Dokl. AN SSSR, 244 (1979), 1093–1096 | MR | Zbl

[10] Bianco L., Blazewicz J., Dell'Ohno P., Drozdowski M., “Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors”, Ann. Oper. Res., 58 (1995), 493–517 | DOI | MR | Zbl

[11] Blazewicz J., Dell'Ohno P., Drozdowski M., Speranza M. G., “Scheduling multiprocessor tasks on three dedicated processors”, Inf. Process. Lett., 41 (1992), 275–280 ; “Corrigendum”, Inf. Process. Lett., 49 (1994), 269–270 | DOI | MR | Zbl | MR | Zbl

[12] Borisovsky P. A., Dolgui A., Eremeev A. V., “Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder”, Eur. J. Oper. Res., 195:3 (2009), 770–779 | DOI | Zbl

[13] Dolgui A., Eremeev A. V., Kovalyov M. Y., Multi-product lot-sizing and scheduling on unrelated parallel machines, Res. Report No 2007-500-011, Ecole des Mines de St.-Etienne, St.-Etienne, 2007, 15 pp.

[14] Drozdowski M., “Scheduling multiprocessor tasks – an overview”, Eur. J. Oper. Res., 94 (1996), 215–230 | DOI | Zbl

[15] Feige U., Kilian J., “Zero knowledge and the chromatic number”, J. Comput. Syst. Sci., 57:2 (1998), 187–199 | DOI | MR | Zbl

[16] Floudas C. A., Kallrath J., Pitz H. J., Shaik M. A., “Production scheduling of a large-scale industrial continuous plant: short-term and medium-term scheduling”, Comp. Chem. Eng., 33 (2009), 670–686 | DOI

[17] Grötschel M., Lovasz L., Schrijver A., “The ellipsoid method and its consequences in combinatorial optimization”, Combinatorica, 1 (1981), 169–197 | DOI | MR

[18] Håstad J., “Clique is hard to approximate within $n^{1-\varepsilon}$”, Acta Math., 182 (1999), 105–142 | DOI | MR

[19] Holland J. H., Adaptation in natural and artificial systems, Univ. Michigan Press, Ann Arbor, 1975, 183 pp. | MR

[20] Hoogeven J. A., van de Velde S. L., Veltman B., “Complexity of scheduling multiprocessor tasks with prespecified processors allocations”, Discrete Appl. Math., 55 (1994), 259–272 | DOI | MR

[21] Ierapetritou M. G., Floudas C. A., “Effective continuous-time formulation for short-term scheduling. I. Multipurpose batch process”, Ind. Eng. Chem. Res., 37 (1998), 4341–4359 | DOI

[22] Itai A., Papadimitriou C. H., Szwarcfiter J. L., “Hamilton paths in grid graphs”, SIAM J. Comput., 11:4 (1982), 676–686 | DOI | MR | Zbl

[23] Jansen K., Porkolab L., “Preemptive scheduling with dedicated processors: applications of fractional graph coloring”, J. Scheduling, 7:1 (2004), 35–48 | DOI | MR

[24] Kubale M., “Preemptive versus nonpreemptive scheduling of biprocessor tasks on dedicated processors”, Eur. J. Oper. Res., 94 (1996), 242–251 | DOI | Zbl

[25] Lin X., Floudas C. A., Modi S., JuhaszN. M., “Continuous-time optimization approach for medium-range production scheduling of a multiproduct batch plant”, Ind. Eng. Chem. Res., 41 (2002), 3884–3906 | DOI

[26] Papadimitriou C. H., Computational complexity, Addison Wesley, Reading, MA, 1994, 540 pp. | MR | Zbl

[27] Reeves C. R., “Genetic algorithms for the operation researcher”, INFORMS J. Comput., 9:3 (1997), 231–250 | DOI | Zbl

[28] Rudolph G., “Finite Markov chain results in evolutionary computation: a tour d'horizon”, Fundam. Inform., 35:1–4 (1998), 67–89 | MR | Zbl