A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem

Wei-Shung CHANG, Chiuh-Cheng CHYU

.

DOI: 10.4236/jsea.2009.25042                

Abstract

In this paper, we propose a multi-criteria machine-schedules decision making method that can be applied to a produc-tion environment involving several unrelated parallel machines and we will focus on three objectives: minimizing makespan, total flow time, and total number of tardy jobs. The decision making method consists of three phases. In the first phase, a mathematical model of a single machine scheduling problem, of which the objective is a weighted sum of the three objectives, is constructed. Such a model will be repeatedly solved by the CPLEX in the proposed Multi-Objective Simulated Annealing (MOSA) algorithm. In the second phase, the MOSA that integrates job clustering method, job group scheduling method, and job group – machine assignment method, is employed to obtain a set of non-dominated group schedules. During this phase, CPLEX software and the bipartite weighted matching algorithm are used repeatedly as parts of the MOSA algorithm. In the last phase, the technique of data envelopment analysis is applied to determine the most preferable schedule. A practical example is then presented in order to demonstrate the applicability of the proposed decision making method.

Keywords

Multi-Objective Optimization, Unrelated Parallel Machines Scheduling, Simulated Annealing Algorithm, Integer Programming Models, Multi-Criteria Decision Making

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	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 Transactions, Vol. 34, No. 11, pp. 921–931, 2004.
[2]	M. K. Richard, “Reducibility among combinatorial prob-lems,” in R. E. Miller and J. W. Thatcher (editors): Com-plexity of Computer Computations, pp. 85–103, Plenum, New York, 1972.
[3]	M. Pfund, J. W. Fowler, and J.N.D. Gupta, “A survey of algorithms for single and multi-objective unrelated paral-lel-machine deterministic scheduling problems,” Journal of the Chinese Institute of Industrial Engineers, Vol. 21, No. 3, pp. 230–241, 2004.
[4]	R. Logendran, B. McDonell, and B. Smucker, “Schedul-ing unrelated parallel machines with sequence-dependent setups,” Computers and Operations Research, Vol. 34, No. 11, pp. 3420–3438, 2007.
[5]	M. A. Hariri and C. N. Potts, “Heuristics for sched uling unrelated parallel machines,” Computers and Operations Research, Vol. 18, No. 3, pp. 323–331, 1991.
[6]	M. Weng, J. Lu, and H. Ren, “Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective,” International Journal of Pro-duction Economics, Vol. 70, pp. 215–226, 2001.
[7]	J. Bank and F. Werner, “Heuristic algorithms for unre-lated parallel machine scheduling with a common due date, release dates, and linear earliness and tardiness pen-alties,” Mathematical and Computer Modelling, Vol. 33, pp. 363–383, 2001.
[8]	A. Glass, C. N. Potts, and P. Shade, “Unrelated parallel machine scheduling using local search,” Mathematical and Computer Modeling, Vol. 20, No. 2, pp. 41–52, 1994.
[9]	B. Srivastava, “An effective heuristic for minimizing make- span on unrelated parallel machines,” Journal of the Operational Research Society, Vol. 49, pp. 886–894, 1997.
[10]	W. Kim, K. H. Kim, W. Jang, and F. F. Chen, “Unrelated parallel machine scheduling with setup times using simu-lated annealing,” Robotics and Computer Integrated Manufacturing, Vol. 18, No. 3-4, pp. 223–231, 2002.
[11]	W. Kim, D. G. Na, and F. F. Chen, “Unrelated parallel machine scheduling with setup times and total weighted tardiness objective,” Robotics and Computer Integrated Manufacturing, Vol. 19, No.1-2, pp. 173–181, 2003.
[12]	R. Logendran and F. Subur, “Unrelated parallel machine scheduling with job splitting,” IIE Transactions, Vol. 36, No. 4, pp. 359–72, 2004.
[13]	J. F. Chen and T. H. Wu, “Total tardiness minimization on unrelated parallel machine scheduling with auxiliary equipment constraints,” Omega-International Journal of Management Science, Vol. 34, pp. 81–89, 2006.
[14]	J. F. Chen, “Minimization of maximum tardiness on un-related parallel machines with process restrictions and setups,” International Journal of Advanced Manufacturing Technology, Vol. 29, No. 5, pp. 557–563, 2006.
[15]	S. Martello, F. Soumis, and P. Toth, “Exact and approxi-mation algorithms for makespan minimization on unre-lated parallel machines,” Discrete Applied Mathematics, Vol. 75, pp. 169–188, 1997.
[16]	Lancia, “Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the make- span,” European Journal of Operational Research, Vol. 120, pp. 277–288, 2000.
[17]	C. F. Liaw, Y. K. Lin, C. Y. Cheng, and M. Chen, “Scheduling unrelated parallel machines to minimize total weighted tardiness,” Computers and Operations Research, Vol. 30, pp. 1777–1789, 2003.
[18]	P. L. Rocha, M. G. Ravetti, G. R. Mateus, and P. M. Par-dalos, “Exact algorithms for a scheduling problem with unrelated parallel machines and sequence and ma-chine-dependent setup times,” Computers and Operations Research, Vol. 35, No. 4, pp. 1250–1264, 2008.
[19]	V. Suresh and D. Chaudhuri, “Bicriteria scheduling prob-lem for unrelated parallel-machines,” Computers and In-dustrial Engineering, Vol. 30, pp. 77–82, 1996.
[20]	K. Jansen and L. Porkolab, “Improved approximation schemes for scheduling unrelated parallel-machines,” ACM Symposium on Theory of Computing, pp. 408–417, 1999.
[21]	S. Kirkpatrick, Jr. C. D. Gelatt, and M. P. Vecchi, “Opti-mization by simulated annealing,” Science, Vol. 220, pp. 671–680, 1983.
[22]	N. E. Collins, R. W. Eglese, and B. L. Golden, “Simulated annealing—an annotated bibliography,” American Journal of Mathematical and Management Sciences, Vol. 8, pp. 209–307, 1988.
[23]	R. B. Rutenbar, “Simulated annealing algorithms: An overview,” IEEE Circuits and Devices Magazine (Janu-ary), pp. 19–26, 1989.
[24]	R. W. Eglese, “Simulated annealing: A tool for opera-tional research,” European Journal of Operational Re-search Vol. 46, No. 3, pp. 271–281, 1990.
[25]	B. Suman and P. Kumar, “A survey of simulated anneal-ing as a tool for single and multiobjective optimization,” Journal of the Operational Research Society, Vol. 57, No. 10, pp. 1143–1160, 2006.
[26]	R. T. Clemen and T. Reilly, “Making hard decisions,” Duxbury, Toronto, 2001.
[27]	P. Andersen and N. C. Petersen, “A procedure for ranking efficient units in data envelopment analysis,” Manage-ment Science, Vol. 39, pp. 1261–1264, 1993.
[28]	D. Slottje, G. W. Scully, J. G. Hirschberg, and K. J. Hayes, “Measuring the quality of life across countries: A multi-dimensional analysis,” Westview Press, Boulder, CO, 1991.
[29]	M. Pinedo, “Scheduling theory: Algorithms and systems,” Prentice-Hall, Inc., A Simon & Schuster Company Engle-wood Cliffs, New Jersey, pp. 10, 1995.
[30]	A. Charnes, W. W. Cooper, and E. Rhodes, “Measuring the efficiency of decision making units,” European Jour-nal of Operational Research, Vol. 2, pp. 429–444, 1978.