A bi-criteria optimization model for parallel machine scheduling: game theoretic vs genetic algorithms
Abstract
This paper considers a problem for scheduling jobs on two identical parallel machines, the aim was to minimize two criteria in particular, makespan and total flow time. In order to solve this problem, two approaches were considered. A mechanism was proposed as an approach to solve this type of problem with a setting of a 2-player non-cooperative game, under the framework of a 2x2 non-sum zero matrix; each player looking after one of the criteria suggested in the scheduling problem. On the other hand, a Genetic Algorithm, known as Strength Pareto Evolutionary Algorithm (SPEA), was applied to the problem. The comparison between both approaches suggests a complementarity among rational agents approach models and machine enforced solution approaches. The resulting Pareto Front set of points were plotted and curves were compared, showing promising results for game theoretic applications to scheduling under multiple objectives.Downloads
References
V. Suresh and D. Chaudhuri, “Bicriteria scheduling problem for unrelated parallel machines,” Comput. Ind. Eng., vol. 30, no. 1, pp. 77–82, Jan. 1996. DOI:10.1016/0360-8352(95)00028-3
L. Yu, H. M. Shih, M. Pfund, W. M. Carlyle, and J. W. Fowler, “Scheduling of unrelated parallel machines: an application to PWB manufacturing,” IIE Trans., vol. 34,no. 11, pp. 921–931. DOI: 10.1023/A:1016185412209
M. Pfund, L. Yu, J. W. Fowler, And M. Carlyle, “TheImpacts Of Variability On Scheduling Approaches For A Printed Wiring Board Assembly Operation,” J. Electron. Manuf., vol. 11, no. 01, pp. 19–31, Mar. 2002. DOI:10.1142/S0960313102000242
Y. Yang and L. Tang, “Local Search Heuristic for Multiple Objective Coil Scheduling Problem on Unrelated Parallel Machines,” in 2009 International Joint Conference on Computational Sciences and Optimization, 2009, vol. 2, pp. 777–780. DOI: 10.1109/CSO.2009.402
Y.-K. Lin, J. W. Fowler, and M. E. Pfund, “Multiple-objective heuristics for scheduling unrelated parallel machines,” Eur. J. Oper. Res., vol. 227, no. 2, pp. 239–253, Jun. 2013. DOI: 10.1016/j.ejor.2012.10.008
C. Low, Y. Yip, and T.-H. Wu, “Modelling and heuristics of FMS scheduling with multiple objectives,” Comput. Oper. Res., vol. 33, no. 3, pp. 674–694, Mar. 2006. DOI:10.1016/j.cor.2004.07.013
M. J. Geiger, “Solving multi-objective scheduling problems— An integrated systems approach,” in Artificial Intelligence in Theory and Practice, vol. 217, M. Bramer, Ed. Springer US, 2006, pp. 493–502. DOI: 10.1007/978-0-387-34747-9
G. Kulcsár And M. K. Forrai, “Solving Multi-Objective Production Scheduling Problems Using A New Approach,” Prod. Syst. Inf. Eng., vol. 5, pp. 81–94, 2009.
S. Bandyopadhyay and R. Bhattacharya, “Solving multi-objective parallel machine scheduling problem by a modified NSGA-II,” Appl. Math. Model., vol. 37, no. 10–11, pp. 6718–6729, Jun. 2013. DOI: 10.1016/j.apm.2013.01.050
S. A. Torabi, N. Sahebjamnia, S. A. Mansouri, and M. A. Bajestani, “A particle swarm optimization for a fuzzy multi-objective unrelated parallel machines scheduling problem,” Appl. Soft Comput., vol. 13, no. 12, pp. 4750– 4762, Dec. 2013. DOI: 10.1016/j.asoc.2013.07.029
E. Kutanoglu and S. D. Wu, “An Incentive Compatible Mechanism for Distributed Resource Planning,” pp. 28, 2001.
S. D. W. Erhan Kutanoglu, “An Auction-Theoretic Modeling of Production Scheduling to Achieve Distributed Decision Making,” Ph.D. dissertation, Dept. Ind. Man. Sys. Eng., Lehigh Univ, Bethlehem, PA, 1997.
A. Archer and E. Tardos, “Truthful mechanisms for one-parameter agents,” in Proceedings 2001 IEEE International Conference on Cluster Computing, 2001, pp.482–491. DOI:10.1109/SFCS.2001.959924
E. Even-dar, A. Kesselman, and Y. Mansour, “Convergence time to nash equilibria,” School of Computer Science, Tel Aviv Univ., p. 17, 2003.
N. Nisan, “Algorithms for Selfish Agents,” in STACS 99 Lecture Notes in Computer Science, vol. 1563, C. Meinel and S. Tison, Eds. Berlin, Heidelberg: Springer Berlin Heidelberg, 1999, pp. 1–15.
G.-Q. Zhang, J.-J. Wang, and Y.-J. Liu, “Scheduling Jobs with Variable Job Processing Times on Unrelated Parallel Machines,” Sci. World J., no. 242107, pp. 1–7, 2014. DOI: 10.1155/2014/242107
B. Heydenreich, R. Müller, and M. Uetz, “Games and Mechanism Design in Machine Scheduling-An Introduction,” Prod. Oper. Manag., vol. 16, no. 4, pp. 437–454, Jan. 2009. DOI: 10.1111/j.1937-5956.2007.tb00271.x
D. R. Rios, C. R. Pinto, and C. Paternina-Arboleda, Game Theoretic Approaches to Parallel Machine Scheduling: A Bi-objective Optimization Problem Viewed as a Non-cooperative Game of Two Players. LAP Lambert Academic Publishing, pp.176, 2012.
E. Zitzler and L. Thiele, An Evolutionary Algorithm for Multiobjective Optimization: The Strength Pareto Approach. Zurich: TIK, 1998.
A. Cama Pinto, E. De la Hoz Franco, and D. Cama Pinto, “Las redes de sensores inalámbricos y el internet de las cosas,” INGE CUC, vol. 8, no. 1, pp. 163–172, 2012.
Y. Donoso and R. Fabregat, Multi-Objective Optimization in Computer Networks Using Metaheuristics. Boston, MA: Auerbach Publications, pp. 472, 2007.
C. E. Gómez Montoya, C. A. Candela Uribe, and L. E. Sepúlveda Rodríguez, “Seguridad en la configuración del servidor web Apache,” INGE CUC, vol. 9, no. 2, pp. 31–38, 2013.
E. Gutierrez and G. Mejía, “Evaluación de los algoritmos Genéticos para el problema de Máquinas en Paralelo con Tiempos de Alistamiento Dependientes de la Secuencia y Restricciones en las Fechas de Entrega.” p. 6, 2006.
P. M. França, A. S. Mendes, and P. Moscato, “Memetic algorithms to minimize tardiness on a single machine with sequence-dependent setup times,” in Proceedings of the 5th International Conference of the Decision Sciences Institute, 1999, pp. 1708–1710.
A. Gómez Cabrera and A. R. Orozco Ovalle, “Simulación digital como herramienta para la gestión del conocimiento en la construcción de edificaciones en concreto,” INGE CUC, vol. 10, no. 1, pp. 75–82, 2014.
K. Deb and D. Kalyanmoy, Multi-Objective Optimization Using Evolutionary Algorithms. New York, NY: John Wiley & Sons, Inc., pp. 249-258, 2001
J. D. Schaffer, R. A. Caruana, L. J. Eshelman, and R. Das, “A study of control parameters affecting online performance of genetic algorithms for function optimization,” in Proceedings of the third international conference on Genetic algorithms, 1989, pp. 51–60
A. P. Cortés Vásquez, “Sistema de Aprendizaje de Patrones de Navegación Web Mediante Gramáticas Probabilísticas de Hipertexto,” INGE CUC, vol. 11, no. 1, pp. 72–78, 2015. Doi: 10.17981/ingecuc.11.1.2015.07
E. Altman, T. Başar, T. Jiménez, and N. Shimkin, “Routing into Two Parallel Links: Game-Theoretic Distributed Algorithms,” J. Parallel Distrib. Comput., vol. 61, no. 9, pp. 1367–1381, Sep. 2001. DOI: 10.1006/jpdc.2001.1754
Published papers are the exclusive responsibility of their authors and do not necessary reflect the opinions of the editorial committee.
IJMSOR respects the moral rights of its authors, whom must cede the editorial committee the patrimonial rights of the published material. In turn, the authors inform that the current work is unpublished and has not been previously published.
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.
