Actas de congresos
Makespan Minimization On Parallel Processors: An Immune-based Approach
Registro en:
Proceedings Of The 2002 Congress On Evolutionary Computation, Cec 2002. Ieee Computer Society, v. 1, n. , p. 920 - 925, 2002.
10.1109/CEC.2002.1007048
2-s2.0-84901436902
Autor
Costa A.M.
Vargas P.A.
Von Zuben F.J.
Franca P.M.
Institución
Resumen
This work deals with the problem of scheduling jobs to identical parallel processors with the goal of minimizing the completion time of the last processor to finish its execution (makespan). This problem is known to be NP-Hard. The algorithm proposed here is inspired by the immune systems of vertebrate animals. The advantage of combinatorial optimization algorithms based on artificial immune systems is the inherent ability to preserve a diverse set of near-optimal solutions along the search. The results produced by the method are compared with results of classical heuristics. © 2002 IEEE. 1
920 925 Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Optimization and approximation in deterministic sequencing and scheduling: A survey (1979) Annals of Discrete Mathematics, 5, pp. 287-326 Bruno, J., Coffman, E.G., Sethi, R., Scheduling independent tasks to reduce mean finishing time (1974) Communications of the ACM, 17 (7), pp. 382-387 Graham, R.L., Bounds on multiprocessing timing anomalies (1969) SIAM J.Applied Mathematics, 17, pp. 416-429 Coffman, E.G., Garey, M.R., Johnson, D.S., An application of bin-packing to multiprocessor scheduling (1978) SIAM J. Comput., 7, pp. 1-17 Lee, C., Massey, J.D., Multiprocessor scheduling combining LPT and multifit (1988) Discrete Applied Mathematics, 20, pp. 233-242 Ho, J.C., Wong, J.S., Makespan minimization for m parallel identical processors (1995) Naval Research Logistics, 42, pp. 935-948 Blackstone Jr., J.H., An improved heuristic for minimizing makespan among m identical parallel processors (1996) Comp, and Indust. Engn, 5, pp. 279-287 Franca, P.M., Gendreau, M., Laporte, G., Muller, F.M., A composite heuristic for the identical parallel machine scheduling problem with minimum makespan objective (1994) Computers & Operations Research, 21 (2), pp. 205-210 Piersma, N., Dijk, W.V., A local search heuristics for unrelated parallel machine scheduling with efficient neighborhood search (1996) Mathematic Comput. Modelling, 24, pp. 11-19 Min, L., Cheng, W., A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines (1999) Artificial Intelligence in Engendering, 13, pp. 399-403 Cheng, R., Gen, M., Parallel machine scheduling problems using memetic algorithms (1997) Comp, and Indust. Engn, 33, pp. 761-764 Dasgupta, D., (1998) Artificial Immune Systems and Their Aplications, , Springer Verlag Hofmeyer, S.A., Forrest, S., Architecture for an artificial immune system (2000) Evolutionary Computation, 7 (1), pp. 45-68 Mori, M., Tsukiyama, M., Fukuda, T., Artificial immunity based management system for a semiconductor production line (1997) Proc. of the IEEE Systems, Man and Cybernetics Conference, pp. 851-855 Hart, E., Ross, P., Nelson, J., Producing robust schedules via an artificial immune system (1998) ICEC, pp. 464-469 Russ, S.H., Lambert, A., King, R., Rajan, R., Reese, D., An artificial immune system model for task allocation (1999) Proc. of the Symposium on High Performance Distributed Computing De Castro, L.N., Von Zuben, F.J., The clonal selection algorithm with engineering applications (2000) GECCO 2000 - Workshop Proceedings, pp. 36-37 Tan, K.C., Narasimhan, R., Minimizing tardiness on a single processor with sequence-dependent setup times: A simulated annealing approach (1997) Omega, Int. Journal Mgmt. Science, 25 (6), pp. 619-634 Lai, K.K., Chan, J.W.M., Developing a simulated annealing algorithm for the cutting stock problem (1997) Comp, and Indust. Engn, 32 (1), pp. 115-127 Li, Y., Wang, D., A semi-infinite programming model for earliness/tardiness production planning with simulated annealing (1997) Mathematical and Computer Modelling, 37 (1-2), pp. 277-280 Tonegawa, S., Somatic generation of antibody diversity (1983) Nature, 302, pp. 575-581 Tonegawa, S., The molecules of the immune system (1985) Scientific American, 253 (4), pp. 104-113 Berreta, R., Moscato, P., (1999) The Number Partitioning Problem: An Open Challenge for Evolutionary Computation ?, , Chapter 17 of New ideas in optimization, D. Corne, F. Glover, and M. Dorigo, (eds.), MacGraw Hill Korf, R., A complete anytime algorithm for number partition ing (1998) Artificial Intelligence, 106 (2), pp. 181-203