### Paper Menu >>

### Journal Menu >>

J. Software Engineering & Applications, 2009, 2: 323-329 doi:10.4236/jsea.2009.25042 Published Online December 2009 (http://www.SciRP.org/journal/jsea) Copyright © 2009 SciRes JSEA 323 A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem Wei-Shung CHANG, Chiuh-Cheng CHYU Department of Industrial Engineering and Management, Yuan-Ze University, Taiwan, China. Email: s948905@mail.yzu.edu.tw, iehshsu@saturn.yzu.edu.tw Received August 6th, 2009; revised August 31st, 2009; accepted September 7th, 2009. 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 1. Introduction Parallel machine scheduling problems have been exten- sively studied in the literature and widely used in many manufacturing environments, such as the drilling opera- tion in a PWB line [1] and glass etch polishing process in the TFT-LCD manufacture. In many real-life situations, the used machines are not always identical in perform- ance. They are different because they were purchased at different times or for different considerations. Some ma- chines may spend much more time on a particular job than others because of their age or design. Consequently, the layout of unrelated parallel machines is more com- mon than identical parallel machines in real manufactur- ing environments. The unrelated parallel machine sched- uling problem (UPMSP) is more difficult than the identi- cal case. Since the latter belongs to NP hard [2], the UPMSP is also NP hard. For further knowledge and re- cent findings regarding the UPMSP, we refer to [3–4]. The problem solving approach to the UPMSP can be classified into two categories: metaheuristics and exact solution method. In metaheuristics, Hariri and Potts [5] proposed a two-phase method to solve the UPMSP with the objective of minimizing makespan (Cmax), where the first phase applies an integer programming technique and the second uses the earliest completion time rule to com- plete the final schedule of the UPMSP. Weng et al. [6] proposed seven heuristics for the UPMSP with job se- quence dependent setup times and the objective of mini- mizing the weighted mean flow time. Two priority rules, shortest processing time (SPT) and the minimum sum of setup time and processing time, are respectively em- ployed in the heuristics. The numerical results indicated that their algorithms are capable of finding quality solu- tions to problems involving 120 jobs with 20 machines in short computational times. Bank and Werner [7] devel- oped a constructive and iterative algorithm to solve the UPMSP with time window constraints on the job release dates and with the objective of minimizing the total weighted lateness. Glass et al. [8] developed a genetic algorithm (GA), simulated annealing (SA), and tabu search (TS) to solve the UPMSP without the sequence dependent setup time constraints. Their experiments conclude that GA per- forms no better than the other two algorithms. Sirvastava [9] proposed a TS algorithm that could find high quality solutions in a short time for a part of the same instances. Kim et al. [10–11] proposed an SA to solve the A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem 324 UPMSP with a goal of total tardiness minimization, while taking into consideration job sequence-dependent set up times. Logendran et al. [4,12] developed a TS for the same problem with additional considerations of dynamic release dates and time window machine availability, where the objective was to minimize the sum of weighted tardiness jobs. Chen [13] presented a record-to-record algorithm with tabu list to solve the UPMSP with the goal of minimizing the maximum tardiness. This paper also presented a threshold accepting algorithm with tabu list to solve the UPMSP to minimize the total tardiness. The branch and bound (B&B) methods are commonly used to optimally solve the UPMSP in the literature [14–18]. Most research on the UPMSP has been focused on a single objective only and there have been comparatively fewer studies on the multi-objective UPMSP. Suresh et al. [19] developed a TS for UPMSP with two objectives: minimizing the maximum makespan (Cmax) and the maximum tardiness. The tabu list keeps the record of newly found non-dominated solutions. Jansen et al. [20] modified the TS by Suresh et al. and solve the UPMSP with the objectives of minimizing Cmax and cost of scheduling. In this paper, a simulated annealing that interacts with the commercial software package CPLEX is developed for solving the UPMSP with three objec- tives – minimizing Cmax, total flow time, and total num- ber of tardy jobs. Since only one schedule will be im- plemented in a real situation, a decision procedure is suggested to make the most preferable choice of the candidate solutions. Simulated annealing (SA) has been known as a com- pact and robust technique to solve many NP-hard prob- lems, including both single objective and multi-objective ones. It can provide excellent solutions to these problems with a substantial reduction in computational time. SA was first introduced by [21]. We refer to [22–24] for sur- veys on single objective SA, and [25] for surveys on multi-objective SA. The remainder of this paper is structured as follows. Section 2 describes the problem under study. Section 3 presents the proposed solution approach. Section 4 pre- sents the numerical results from the proposed method used to solve a problem with real life data. Finally, Sec- tion 5 concludes the paper with implications for future research. 2. Problem Description The aim of this study is to develop a systematic solution method for determining the most preferred schedule among a non-dominated set of schedules found by the proposed hybrid simulated annealing algorithm. In this section, first of all, notations used in this paper are intro- duced; secondly, the studied problem is described, in- cluding a multi-objective mathematical model. 2.1 Notations Symbols: i: machine index, i = 1,…, M j: job index, j = 1,…, J M: total number of machines used J: total number of jobs to be processed pij: processing time of job j performed by machine i sij: set up time for job j on machine i dj: due date of job j Gm: set of jobs in group m, m = 1,…, M Decision variables: Cmax: maximum makespan (completion time) among all machines max i C: makespan of machine i Cij: completion time of job j on machine i Tij: tardiness of job j on machine i, Tij = max{0，Cij – dj} Uij: tardiness state of job j if it is processed on machine i: value is 1 if tardy;otherwise value is 0; number of tardy jobs for machine i yij: value is 1 if job j is assigned to machine i; value is 0 otherwise xijk: value is 1 if both jobs j and k are assigned to ma- chine i and job j immediately precedes job k; value is 0 otherwise 2.2 Problem Definition We consider the following manufacturing environment: there are I different machines in parallel with a total number of J jobs to be processed, and a job refers to a customer’s order. The problem under study assumes that each job may have different processing times depending on the assigned machine, each machine will process one job at a time, and the processing is non-preemptive. The setup time of each job is assumed to be machine depend- ent but not job sequence dependent; thus, the setup time is included in the processing time. The scheduling prob- lem considered in this study aims to minimize three ob- jectives simultaneously: Cmax, total flow time, and total number of tardy jobs. 2.2.1 Mathematical Formulation max 11 11 (, , MJ MJ ij ij ijij ) M inimize CCU (1) max max . . i s tC Ci j (2) max , i ij CC i (3) max 1 J i ij ij j Cpy i (4) 0; C , ijijij j TT dij (5) Copyright © 2009 SciRes JSEA A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem325 ijbig ij TMU ,ij (6) (1 ) ik ikbigijkij CpMx C ,,ijk (7) 1, , J ijk ij kkj x yi j j (8) 0 , ij Ci , ,0,1 , ij ij; y Ui j 0,1 ,, ijk x ijk (9) where Mbig is a big number. In the model, Equation (1) presents the three objective quality set (2) shows the first ob non-dominated schedules (or alternatives) select the most be adopted: 1) se lem solving method as the lowing strategy: 1) pr to represent a nds to the set gi functions of the UPMSP; ine jective is to minimize the maximin makespan of all machines; constraint set (3) specifies the makespan of each machine; constraint set (4) defines the makespan of each machine; constraint set (5) defines the tardiness of each job; constraint sets (5) and (6) together define the number of tardy jobs; constraint set (7) specifies the starting time relationships between jobs under a certain processing sequence in the same group. Equation set (8) ensures that each individual job will be processed by only one machine. 2.2.2 Multi-Criteria Decision Making Given a set of to the problem under study, we seek to preferable one. Various approaches can be applied to solve this decision problem. Some well known methods are as follows: 1) construct a multi-attribute utility func- tion [26] which is defined on the objective space, and then take the alternative with the maximum utility value; 2) assign priorities to objectives and take the alternative with the best Lexicographic order; 3) select the alterna- tive that has the maximum AP efficiency ratio in data development analysis [27] or that has the maximum score using principle component analysis [28]. In the case that there are too many non-dominated so- lutions, a simple three-stage method will lect a reasonable number of diversified solutions; 2) decide what the inputs and the outputs should be; 3) compute the AP efficiency ratio and choose the one which ranks first. 3. Problem Solving Method In this paper, we developed a prob that uses the simulated annealing (SA) algorithm main framework and employs the CPLEX optimizer to solve the multi-objective scheduling problem with an assigned weight vector. The acceptance probability takes into account the upgrading or downgrading of each indi- vidual objective function at each step of generating a neighborhood solution, and is defined as the product of each individual acceptance probability with respect to the change of each objective at each step. In order to produce an acceptable number of non- dominated schedules, we adopt the fol edetermine a set of weight vectors for the three- objec- tive scheduling problem; 2) solve optimally or near opti- mally the multi-objective scheduling problem with the target of minimizing the weighted sum of the objectives for each weight vector; 3) find higher quality diversified solutions using different initial solution. In the study, three priority rules, EDD (early due date), SPT (shortest processing time), and CR (critical ratio) are used to gen- erate an initial solution. 3.1 Encoding and Decoding Scheme In the proposed SA, a job list is used schedule of UPMSP. A sublist m correspo of jobs assigned to group m. To generate an initial job list, all jobs are first sorted first based on a priority rule, and then placed one by one into each sublist according to the order of the list. In doing so, a set of job groups is formed, with the number of groups equal to the number of ma- chines. Given a job list, a neighborhood solution will be generated by performing a 3-opt operation on the list. Figure 1 illustrates the decoding process using 15 jobs and four machines. First, a weight vector (1, 2, 3) is ven for the three objectives In step 1, 15 jobs are grouped and sequenced according to the priority rule. In the example, group 1 (sublist 1) contains jobs 2, 5, 6, and 13. In step 2, based on the results in step 1, we can obtain an initial solution for each group-machine pair and fur- ther improve it by single machine scheduling heuristic (SMSH). Note that in this step the three objective values are normalized using Equations (12)–(14). Since there are four machines, a 4 by 4 yielding 16 group-machine pairs are computed. Figure 2 displays the results of step 2. Figure 1. Example of decoding scheme Copyright © 2009 SciRes JSEA A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem 326 332211 objective sum Weighted fff Figure 2. Applying SMSH to all group-machine pairs Figure 3. Optimal group-machine matching by BWMA Finally, the bipartite weighted matching algorithm (BW MA) is applied to find the optimal group-machine mat- ching and this concludes the decoding scheme (Figure 3). 3.1.1 Single Machine Scheduling Problem with a Weighted Sum of Objectives This section presents the mathematical model of the weighted sum objectives of the single machine schedul- ing problem, which will then be solved by the CPLEX solver in the interactive SA algorithm. Given a weight vector, (1, 2, 3) with 1 + 2 +3 = 1, 1, 2, 3 0, and group Gm is assigned to machine i, the mathematical model is as follows: Min , 3 ,, ,123 123 12 (, , )imim im im F ff s.t. (3), (4), (5), (6), (7) for ,m jk G f ,, m ijk jk Gjk 1x m 0 ij m CjG 0, 1 ijk x ,m jk G (11) kG (10) ) (12) where , max minmax 1()/( im iiii fCgg min g , minmax min 2()/() m imii i j jG fChhh (13) , minmax min 3()/() m imii i ij jG fUuuu (14) and (min i g ,min i h,mi i u) and (max i g , n i max h,max i u) are the ideal solution and anti-ideal solution to the three- obschedulin problem, re- sp 3.1.2 Assignment Problems between J Machines Given an assigned weigt vector (1, 2, 3) s {Gm, m = 1,…, M}, a total of M × M single eduling solutions can be crea which corresponds to a group of jobs being a machine. The problem in this step is a bi hted maching problem and will be solved by th ian method. The mathematical model of the group-ma- chine assignment problem is presented as follo jective single machine g ectively. ob Groups and hand a set of job group machine schted, each of processed by partite weig- e Hungar- ws: , 1 (, im i i 123 1 , ) MM m m M in F y s .t. M im y 1i 1 mM = 1，…，(15) 1 1 im m y M i = 1，…，M (16) 0 im y m, i = 1，…，M 3.2 MOSA Algorithm The following presents the MOSA algorithm: 1) Select a wide diversified set = {k : k = 1,…, K}, where each k corresp the kth weight vector of the three objectives. Choose a set of prior- ity rules, Pr = {prl: l = 1, …, L}, which will subse- be used to create the initial solutions. Set the number of temperature levels = NTL, and the number level = ITN. k = 1; l = 1, ntl = 1, T = T1, itn = 1. 2) Apply priority rule prl to generate an initial parti- tioned set of jobs, {Gm: m = 1,…, M}; Compute onds to quently of maximum iterations at each temperature Copyright © 2009 SciRes JSEA A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem327 ,1 (,,) kkk im F23 ; employ the Hunggorithm the group jobs – machines assignment arian al to solve problem; evaluate all objective functions and put them (z1(x), z2(x), z3(x)) be the cor- alized objective values. ted a new m, into a Pareto set of solutions. Let x = current solution with Z(x) = responding non-norm 3) Give a random perturbation and genera partitioned set of jobs. {' m G: = 1,… M}; Com- pute ,123 (, ) kkk im F, ; employ Hungarian algo- rithm to solve the group jobs – machines assign- ment problem and obtain a new solution y; evaluate all objective values: Z(y) = (z1(y), z2(y), z3(y)). Compare y with all solutions in the Pareto set and update the Pareto set, if necessary. If y is archived, make it the current solution by put- 4) 5) probability to e ting x = y and move on to step 7; otherwise compute () () rr r zzyzx , r = 1, 2, 3. Assign acceptance ach of objective functions as fol- lows: pr = 1 if 0 r z; pr = (exp(-/) r zT)k r if 0 r z, r = 1, 2, 3; Acceptance probability = 123 pp p 6) If y is accepted, then set x = y; 7) itn = itn + 1; if (itn > ITN), set ntl = ntl + 1; 1ntl ntl TT . If (ntl ate and output the best solu- tion; otherwise, go to step 2. hoosing the Best Alternative 8) > NTL), termin 3.3 C In makipetitive alterna- tiv a hig taken to complete the pr of th the t schedese two arded as the iomputing. On thot hand, the num jobs represents the number of unsae will instead be taken as anf tardy jobs imply a be the ber of tardybs m th that the setup time of a job is only ma- job-sequence-dependent, and time. s are chosen to construct the initial this paper, we will choose the AP efficiency ratio for ng the best choice among many com es. In the three objectives, a small Cmax usually implies h utilization of machine(s), i.e., how much time is oduction. Furthermore, the sum e completion times of J jobs gives an indication of otal holding or inventory costs incurred by the le [29u]. Thobjectives will be reg nputs when c the AP ratioe her ber of tardy tisfied customers. This valu output. Since a small number o tter performance, we use a total number of jobs minus num jo in a schedule as the performance easure to indicate the level of customers’ satisfaction of at schedule. 4. Numerical Results In this section, the computational characteristics and ef- fectiveness of the proposed interactive SA algorithm are evaluated via a practice example, which arises in the glass etch polishing during the Cell manufacturing stage of the TFT-LCD production process. The glass etch pol- ishing operation is independent of the other manufactur- ing processes, and is required only for some types of TFT-LCD products. In the example, a collection of real life data for four different machines and 21 different products was made. The data contains the information of the processing time of each job (a batch of the same products) on each indi- vidual machine. Our observation indicates that the setup time of a job is approximately the same in each machine, regardless of whichever its preceding job is. But the setup time may be different in different machines. There- fore, it is assumed chine-dependent rather than is included in the processing In the experiment, the SA algorithm was coded in Visual Studio C++. NET and executed on a computer with Intel core dual, 1.8GHz and 2 GB DDR566, and used the CPLEX 10.0 optimizer to solve the weighted sum objective single machine scheduling problem. The parameters setting of the SA is as follows: NTL = 20, ITN = 5, T1 = 100, and = 0.95. Three priority rule solutions. They are early due date (EDD), shortest proc- ess time (SPT), and critical ratio (CR), where CR is de- fined as the ratio of the due date over the average proc- essing time. Table 1 displays the best solutions found Table 1. Best solutions for various weight vector with EDD initial solution λ1 λ2 λ3Cmax Total flow time No. tardy jobs CPU (sec.) 0.1, 0.1, 0.84392105.9 2 201.5 * 0.1, 0.2,0.73441831.48 1 196.9 0.1, 0.3, 0.65562276.01 2 200.2 0.1, 0.4, 0.53671888.4 3 187 0.1, 0.5, 0.43721772.98 3 198.1 0.1, 0.6, 0.35882542.73 1 197.5 0.1, 0.7, 0.24501970.37 1 190.7 0.2, 0.1, 0.75962189.48 0 205.4 0.2, 0.2, 0.65982267.12 2 201.1 0.2, 0.3, 0.57262715.26 0. 1 194.5 0.3, 0.4, 0.33892241.87 3 196.9 1910.4 2 197.0 2, 0.4, 0.44272312.18 2 196.9 0.2, 0.5, 0.33821906.4 3 195.9 0.2, 0.6, 0.24002330.29 3 197.5 0.3, 0.1, 0.64752099.12 1 201.0 * 0.3, 0.2,0.53601774.87 2 203.4 0.3, 0.3, 0.45362103.48 1 210.9 0.3, 0.5, 0.27692890.04 1 194.0 0.4, 0.1, 0.53811924.4 1 199.8 0.4, 0.2, 0.4382 0.4, 0.3, 0.34792138.9 1 202.5 * 0.4, 0.4,0.25272019.48 0 200.1 * 0.5, 0.1,0.42551770.4 3 199.8 0.5, 0.2, 0.33672083.79 2 195.6 0.5, 0.3, 0.24502275.62 1 202.3 0.6, 0.1 ,0.3 0.6, 0.2, 0.2 389 663 1879.73 2471.01 2 1 206.7 197.8 Copyright © 2009 SciRes JSEA A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem 328 Table 2. Nomutions fo in all t max flow time No. tard on-dinant solundrials λ1 λ2 λ3CTotal y jobs 0.4, 0.4, 0.2 527 2019.48 0 0.3, 0.1, 0.6 304 1794.73 1 48.51 2 51 2 0.2, 0.3, 0.5 241 17 0.4, 0.4, 0.2 245 1746. Tk theternativeased oAP ra 1 Output CCR o able 3. Rans of four als bn the tio Alternatives Input Input 2 AP rati 1 527 1.000 0.933 2019.48 0.933 2 304 0.952 1.000 0.905 1.000 0.905 0.999 1794.73 1.024 3 2411748.51 1.017 4 2451746.51 0.999 Nuesults ofENA rCma flow time No. tard Table 4.merical r AR Dispatching ules x Total y jobs SPT 262 2638 15 EDD 294 3391 20 CR 597 4926 21 wito eweighand the EDD initial soldernd a limber of hi quality non-domfor ght vector, the SA ill output the solution with the minimum weighted ob- observed from Table 1, only four local non-domi- nns were fitDal . Hen gln- natedlutionsndAresin 2. The first one wrodithDDl sn, the second wite SPT, and tt tth . Three local nomsos in Table re emoved when compared with the second and third solu- tions in Ta mdule amse four alhe pr6] is applihen aing tdure, thelues of Cmax anflow time are d as inputse value of Cmax can be viewe the te of the equipments nd schedule should be the most prefer- ab iding quality 5. -making process as to e. In addition, for problems of large onary algorithms will be more favor- arlyle, and J. W. h respect tach t vector ution. In or to fimited nugh inated solutions, each wei w jective value. As ated solutio owever, th ound w otally o h the ED ly four initi obal solution on-domire are t so fou by the S, as pented Table as puced w the E initiaolutio h thhe reswo withe CR on-dinated lution1 we r ble 2. To select the ternatives, t ost prefera e ranki ble sche ng procedur ong the oposed by [2 ed. Wpplyhe proce va d total treate otal tim . Th d as used in the production, and the flow time gives an indica- tion of the total holding or inventory costs incurred in the production. The number of tardy jobs occurs in a sched- ule will be viewed as the output, since it represents the number of customers who will not be satisfied with the purchase service. The following scoring method for this output is adopted: (total no. of jobs – total no. of tardy jobs) / (total no. of jobs) Table 3 presents the ranks of the four non-dominated schedules. Both the second and the third schedules have a CCR ratio [30] of one, which implies both are effective. However, a further comparison based on the AP ratio indicates the seco le. The proposed decision-making model is more pro- per if it includes the consideration of the cost of sched- ules. In unrelated parallel machine scheduling problems, a job may take different processing times on different machines, and thus its processing cost may also be dif- ferent when processed by different machines. Table 4 shows the numerical results by applying the simulation software ARENA to the instance using three different dispatching rules commonly used in industry. Clearly, the SPT rule works much better than the other two, but its solution is considerably dominated by the second to fourth solutions in Table 2. The proposed algo- rithm is superior to the professional software in prov solutions for the instance. Conclusions In this paper, we proposed an interactive simulated an- nealing algorithm aimed at searching for a set of near Pareto optimal solutions to the unrelated parallel machine scheduling problem with three objectives: minimizing total completion time, total flow time, and total number of tardy jobs. A commercial optimization software pac- kage IILOG CPLEX is served as a function in the SA algorithm, with the mission of solving optimally the sub- problem - weighted sum objective single machine sched- uling problems. To produce an acceptable number of high quality non-dominated solutions, a unique best schedule is found with respect to each weight vector. The ranking procedure proposed by Andersen and Petersen is then applied to select the most preferable schedule, using total completion time and total flow time as the inputs, and total number of tardy jobs as the output. Further research would include the cost of schedules as one of the inputs in the decision select the best schedul size, hybrid evoluti able than the current method, in which the CPLEX opti- mizer occupies a large percentage of computational time. When solving large size problems, the number of non-dominated solutions would be very large. An inter- esting research direction may be focused on developing a good method for making the best selection among the huge number of near Pareto-optimal solutions. 6. Acknowledgments This research was partially supported by the National Science Council in Taiwan under grant NSC 95-2221- E-155-045. REFERENCES [1] L. Yu, H. M. Shih, M. Pfund, W. M. C Copyright © 2009 SciRes JSEA A Multi-Criteria Decision Making for the Unrelated Parallel Machines Scheduling Problem Copyright © 2009 SciRes JSEA 329 nell, and B. Smucker, “Schedul- Potts, “Heuristics for sched uling unrelated paralers and Operations Research, Vol. 1991. 226, 2001. cal and Computer Modelling, Vol. 33, heuristic for minim ng, and F. F. Chen, “Unrelated achine scheduling with auxiliar llo, F. Soumis, and P. Toth, “Exact and approxi- mation algorithms for makespan minimization on unre- ake- total ti, G. R. Mateus, and P. M. Par- ximation tt, and M. P. Vecchi, “Opti- bibliography,” American Journal Devices Magazine (Janu- 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. McDo 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. lel machines,” Comput 18, No. 3, pp. 323–331, [19] [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– [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,” Mathemati 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 effectiveizing 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. 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. Ja 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 my “M 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. Marte 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 m 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 weighted tardiness,” Computers and Operations Research, Vol. 30, pp. 1777–1789, 2003. [18] P. L. Rocha, M. G. Ravet 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. 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 appro schemes for scheduling unrelated parallel-machines,” ACM Symposium on Theory of Computing, pp. 408–417, 1999. [21] S. Kirkpatrick, Jr. C. D. Gela 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 of Mathematical and Management Sciences, Vol. 8, pp. 209–307, 1988. [23] R. B. Rutenbar, “Simulated annealing algorithms: An overview,” IEEE Circuits and [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, easuring 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. |