prev

next

out of 9

Published on

26-Jun-2016View

219Download

0

Transcript

problems often involve more than one aspect and therefore require bicriteria analysis. In this study, bicriteria two-machineucts). In manufacturing environments this includes obtaining tools, positioning work in process material,uling literature reveals that the research on bicriteria is mainly focused on the single-machine problem as a* Corresponding author.E-mail addresses: teren@kku.edu.tr (T. Eren), erguner@gazi.edu.tr (E. Guner).Applied Mathematics and Computation 183 (2006) 12921300www.elsevier.com/locate/amc0096-3003/$ - see front matter 2006 Elsevier Inc. All rights reserved.returning and adjusting tools, cleaning-up, setting the required jigs and xtures, and inspecting material.The majority of scheduling research on owshops considers setup times negligible or as part of the processingtimes. While this might be justied for some applications, many other situations call for explicit separate setupconsideration; see [17]. An important implication of separate setup times is that the setup on a subsequentmachine may be performed while the job is still in process on the immediately preceding machine. A recentsurvey of scheduling research involving setup times is given by Allahverdi et al. [8] and Cheng et al. [9].Another area of research in the scheduling literature involves the bicriteria problem. The majority ofresearch on scheduling problems addresses only a single criterion while the majority of real-life problemsrequire the decision maker to consider more than a single criterion before arriving at a decision. The sched-owshop scheduling problem with setup times is considered. The objective function of the problem is minimization of theweighted sum of total completion time and total tardiness. An integer programming model is developed for the problemwhich belongs to NP-hard class. Only small size problems with up to 20 jobs can be solved by the proposed integer pro-gramming model. Heuristic methods are also used to solve large size problems. These heuristics are four tabu search basedheuristics and random search method. According to computational results the tabu search based methods are eective innding problem solutions with up to 1000 jobs. 2006 Elsevier Inc. All rights reserved.Keywords: Flowshop scheduling; Bicriteria; Setup times; Integer programming; Heuristic methods1. IntroductionSetup times are dened to be the work to prepare the resource (machine), process, or bench for tasks (prod-A bicriteria owshop scheduling problem with setup timesTamer Eren a,*, Ertan Guner ba Department of Industrial Engineering, Faculty of Engineering, Krkkale University, 71450 Krkkale, Turkeyb Department of Industrial Engineering, Faculty of Engineering and Architecture, Gazi University, 06570 Maltepe, Ankara, TurkeyAbstractMost of research in production scheduling is concerned with the minimization of a single criterion. However, schedulingdoi:10.1016/j.amc.2006.05.160T. Eren, E. Guner / Applied Mathematics and Computation 183 (2006) 12921300 1293result of the diculty of the multiple machines problem. This paper addresses a two-machine owshop sched-uling problem with a bicriteria objective function [10,11].The bicriteria scheduling problems are generally divided into three classes. In the rst class, one of the bicri-teria is considered as the objective to be optimized while the other is considered as a constraint. In the secondclass of problems, both criteria are considered equally important and the problem involves nding ecientschedules. In the third class of problems both criteria are weighted dierently and an objective function asthe sum of weighted functions is dened [10,11]. The problem considered in this paper belongs to this class.To increase system performance of a two-machine owshop, the lowering of work in process as much aspossible is important. The scheduling criterion of total ow time minimization can eectively reduce workin process. Due-date conformance is one of the performance measures most frequently encountered in prac-tical scheduling problems. The total tardiness criterion, in particular, has been a standard way of quantifyingthis conformance. For instance, if several components are to be assembled into a product, then there is nobenet gained from nishing some components early and the tardiness penalty is imposed proportionallyon the delay over all jobs [10,11].In this paper, we consider a bicriteria scheduling problem with separate setup times on two machine ow-shop. The objective function of the problem is minimization of the weighted sum of total completion time andtotal tardiness. The considered problem is denoted as F 2=sji=aPC bP T . This bicriteria problem is an NP-hard problem since the simpler single criterion variations of the problem that are F 2=sji=PC and F 2=sji=PTare already NP-hard problems [12,13].The rest of the study is organized as follows. In Section 2 and Section 3, the problem and the proposed amathematical programming model are described. A random search method and tabu search based methodsthat are used to solve large size problems are presented in the Section 4. The experimental results are givenin the Section 5. Finally, Section 6 provides conclusions and evaluations of the study.2. Problem descriptionThere are n jobs ready to be processed at time zero. Each job has two operations. The rst operation isperformed by the rst machine followed by the second operation that is performed by the second machine.Let pji, sji and dj denote the processing time of ith machine, the setup time of ith machine, and the due dateof the job j, respectively. A job once started on any machine must be completed on it without interruption (i.e.,no preemption is allowed). The machine may not process more than one operation at a time. Let Cj and Tjdenote the completion time and tardiness of the job j respectively.Pnj1Cj andPnj1T j Pnj1 maxfCj dj; 0g total completion time and total tardiness, respectively. The considered problem isdenoted as F 2=sji=aPnj1Cj bPnj1T j.3. The proposed integer programming modelThe proposed model has n2 + 12n variables and 13n constraints, where n is the number of jobs. Assump-tions, parameters and variables used in the model are given as follows:3.1. Assumptions All jobs are available for processing at time zero. Each job must be completed if it is started. Each job has two operations. To make a job on second machine, it must be completed on the rst machine. Processing times are independent of the schedule. Jobs can wait the next machine to become idle. Machines may be idle. Setup times are known and they are not included to processing times. Machines never breakdown and are available throughout the scheduling period. No machine may process more than one operation at the same time.j the number of jobs, j = 1,2, . . . ,n.i the number of machines, i = 1,2.k k k1;2T k P Ck dk ; k 1; 2; . . . ; n: 11294 T. Eren, E. Guner / Applied Mathematics and Computation 183 (2006) 12921300dk : the due date of the kth ranked jobdk Xnj1Zjkdj; k 1; 2; . . . ; n: 53.5. Proposed integer programming modelP Ppki j1Zjkpji; i 1; 2; k 1; 2; . . . ; n; 2s[ki]: the setup time of the kth ranked job at the ith machineski Xkj1Zjksji; i 1; 2; k 1; 2; . . . ; n; 3Ck: the completion time of the kth ranked job at the second machineCk Xkj1X j Xkj1pj2; k 1; 2; . . . ; n: 4. Auxiliary variablesp[ki]: the processing time of the kth ranked job at the ith machineXk3.4Sk: the starting time for the kth ranked job at the rst machine, k = 1,2, . . . ,n.Tk: the tardiness of the kth ranked jobpji the processing time of job j on the ith machine, i = 1,2, j = 1,2, . . . ,n.sji the setup time of job j on the ith machine, i = 1,2, j = 1,2, . . . ,n.dj the due date of job j, j = 1,2, . . . ,n.a the weight for the total completion time, 0 < a < 1.b the weight for the total tardiness, a + b = 1.3.3. Decision variablesZjk: if job j is scheduled at the kth rank to be processed, Zjk = 1, otherwise Zjk = 0, j = 1,2, . . . ,n,k = 1,2, . . . ,n.Xk: the idle time on the second machine between the starting of the kth ranked job and the completion ofthe (k 1)th ranked job, k = 1,2, . . . ,n.Yk: the time between its completion at the rst machine and its begin processing at the second machine forthe kth ranked job, k = 1,2, . . . ,n.Zk: the idle time on the second machine between the completion time of the k 1 ranked job on the secondmachine and the starting time of the kth ranked job on the rst time,Z maxfS C ; 0g; k 1; 2; . . . ; n:3.2. ParametersObjective function: Min Z a C b Twithsearcthis sproceThfor smmethdom4.1. TTa(currecurreneighcurreT. Eren, E. Guner / Applied Mathematics and Computation 183 (2006) 12921300 1295tabu. A tabu move may be allowed if an aspiration criterion is satised. This procedure continues until a cri-terionthe large size problems. Meta-heuristic approaches such as genetic algorithms, simulated annealing, tabuh, etc. are perhaps the most powerful optimization methods and are suitable for scheduling problems. Intudy, we used tabu search based heuristic methods and a random search method as the solutiondures.e considered bicriteria owshop scheduling with separate setup times problem can be solved optimallyall size problems with up to 20 jobs by the proposed integer programming model. Also, ve heuristicods are used to solve large size problems. These heuristics are four tabu search based methods and a ran-search method. These methods are explained in the following sections.abu search heuristicbu search has been used widely in combinatorial optimization. The basic idea is to slightly alter a knownnt) solution in a certain manner (called neighborhood structure) and take the best alteration as the newnt solution. Such altered solutions are called neighbors of the current solution. An operation that yields abor is called a move. To avoid being trapped at a local optima, the best neighbor that is worse than thent solution is allowed to become the new current solution. To avoid cycling, certain moves are marked asConstraints:Xnj1Zjk 1; k 1; 2; . . . ; n; 6Xnk1Zjk 1; j 1; 2; . . . ; n; 7Sk P Sk1 sk1;1 pk1;1; k 2; 3; . . . ; n; 8C12 Z1 s12 X 1 p12;Ck2 Ck1;2 Zk sk;2 X k pk2; k 2; 3; . . . ; n; 9Z1 S1 s1;1 p1;1 Y 1 s1;2 X 1;Zk Sk sk;1 pk1 Y k Ck1;2 sk;2 X k k 2; 3; . . . ; n; 10X 1 S1 s1;1 p11 Y 1 Z1 s1;2;X k Sk sk;1 pk1 Y k Ck1;2 Zk sk;2; k 2; 3; . . . ; n: 11In (1)(5) equations all variables are positive and integer.Constraint (6) species that only one job be scheduled at the kth job priority. Constraint (7) denes thateach job be scheduled only once. Constraint (8) represents that the begin processing time of the kth rankedjob be greater than or equal to the previous jobs completion time at the rst machine. Constraints (9) canbe explained the idle time on the second machine to process the kth ranked job (Xk) equals the starting timefor the kth ranked job on the rst machine (Sk) plus its processing time on the rst machine (pk1) plus the timebetween its completion on the rst machine and begin processing time on the second machine (Yk) minus thecompletion time for the (k 1)th ranked job at the second machine (Ck1). Constraints (10) can be explainedthe idle time on the second machine before its setup operation of kth ranked job, Constraint (11) can beexplained the same way as Constraints (10). All variables should be greater than or equal to zero and Zjkis a binary integer.4. Heuristic methodsMost of the scheduling problems are NP-hard problems. Thats why only the small size problems of thisclass can be solved optimally by enumeration methods such as the branch-and-bound methods, the dynamicprogramming and the integer programming models. However, the real applications in industry require dealingis met [14].In this study, an experimental design was made for dening suitable tabu search parameters and 405 prob-lems were solved. According to experimental results the chosen tabu search parameters in the problem areshown in Table 1. In addition, according to the used initial solutions, the tabu search methods separate fourgroups. For instance, the NEH algorithm is modied our objective function (MNEH) and then the solutionvalue of MNEH is taken as an initial solution at Tabu IV.4.2. Random searchRandom search is a method that selects a specic number of solution point (a sample size) randomly fromthe solution space. Random search evaluates the selected points (sequences) about their objective function val-Table 1Parameters of tabu searchParameters Tabu I Tabu II Tabu III Tabu IVInitial solutions Random Johnson [15] EDD NEH [16]Tabu list length 2np2np2np2npNeighborhood search strategy: API API API APIStopping criterion n Iteration noimprovementn Iteration noimprovementn Iteration noimprovementn Iteration noimprovementTable 3Table 2The experimental set for the small size problemsParameters Alternatives ValuesNumber of job (n) 6 10, 12, 14, 16, 18, 20Processing time (pji) 1 U[1,100]Setup time (sji) 4 U[0,9] U[0,24] U[0,49] U[0,99]Due date (dj) 1 dj sjk Pnj1pj un 1pjWeights (a,b) 3 (0.25,0.75); (0.50,0.50); (0.75,0.25)Number of solved problems 10Total problem 6 1 4 1 3 10 = 7201296 T. Eren, E. Guner / Applied Mathematics and Computation 183 (2006) 12921300The average CPU times of the integer programming model (n 6 20)n Weights (a,b) Setup times (sji)U[0,9] U[0,24] U[0,49] U[0,99]10 (0.25,0.75) 5.09 4.00 3.20 6.7012 32.76 56.50 39.12 52.2414 122.74 229.92 128.97 128.2716 338.87 370.08 302.16 293.5418 959.95 801.16 683.54 537.9220 3429.02 2799.86 2252.47 1834.8510 (0.50,0.50) 6.73 4.56 4.53 10.5512 86.40 56.71 53.87 61.6414 114.87 293.92 134.18 118.6116 255.88 359.71 229.04 248.0818 1188.07 1027.87 849.60 431.9720 3281.21 3089.58 2974.03 2210.3510 (0.75,0.25) 3.66 3.35 3.73 9.0712 35.82 74.17 40.22 61.7514 118.28 222.79 114.18 94.0616 442.14 336.49 235.35 198.6318 957.51 940.27 703.15 548.1420 2635.10 2354.78 2434.45 2446.56ues and identies the best sequence in the sample. The best sequence is stored at the memory and then thisprocess is repeated. When the new best sequence is better than the previous one, the previous sequence isupdated with the new sequence otherwise it does not change. The search is stopped at a prespecied numberof iterations. There are two parameters in random search method: The rst is the specication of the samplesize and the other is the stopping rule. Stopping can be realized either at a certain number of iterations or whenthere is no improvement a given number of consecutive iterations [17,18].In experimental study we took (n 1) as the sample size and no improvement for n repetitions as the stop-ping rule for the problem.0.000.050.100.150.2010 12 14 16 18 20number of job (n)number of job (n)CPU time (sn)CPU time (sn) (sn)randomtabu-Itabu-IITabu-IIITabu-IV0.000.050.100.150.2010 12 14 16 18 20randomtabu-Itabu-IITabu-IIITabu-IV0.150.20randomtabu-IbcT. Eren, E. Guner / Applied Mathematics and Computation 183 (2006) 12921300 1297number of job (n)CPU time0.000.050.1010 12 14 16 18 20tabu-IITabu-IIITabu-IVFig. 1. Heuristic performance for small number of jobs: (a) a = 0.25, b = 0.75; (b) a = 0.50, b = 0.50; (c) a = 0.75, b = 0.25.5. Experimental resultsThe integer programming model was used to nd the optimal solutions of the considered problem usingHyper LINDO/PC 6.01 software package. Tabu search based heuristic methods used in this paper were codedon C++ Builder 5. The experimental design is similar to Rajendran ve Ziegler [19]s and processing times onmachines were generated from a uniform distribution in the ranges [1,100]. The setup times are randomly gen-erated from another uniform distribution on the integers between [0,9], [0,24], [0,49] and [0,99]. Due dates (dj)are dened as follows:0.000.100.200.300.40100 200 300 400 500 600 700 800 900 1000randomtabu-Itabu-IITabu-IIITabu-IV0.000.100.200.300.40100 200 300 400 500 600 700 800 900 1000randomtabu-Itabu-IITabu-IIITabu-IV0.300.40randomtabu-Ibcnumber of job (n)number of job (n)CPU time (sn)CPU time (sn)e (sn)1298 T. Eren, E. Guner / Applied Mathematics and Computation 183 (2006) 129213000.000.100.20100 200 300 400 500 600 700 800 900 1000tabu-IITabu-IIITabu-IVnumber of job (n)CPU timFig. 2. Heuristic performance for a large number of jobs: (a) a = 0.25, b = 0.75; (b) a = 0.50, b = 0.50; (c) a = 0.75, b = 0.25.dj sjk Xnj1pj un 1pj;where sjk is mean sequence-dependent setup time and pj is mean processing time, u is a random number be-tween [0,1]. The experimental set is given in Table 2. As seen from Table 2, totally 720 problems are solved.The average CPU times of the integer programming model (in terms of seconds) in relation to the numberof jobs are given in Table 3. three dierent weight factors are used for the problems.The optimal solutions of the considered problem can be found up to 20 job sizes. To solve large size prob-lems in a short time and to nd the optimal or near optimal solutions, heuristics should be used. For the prob-lem considered, ve heuristic methods were used. Heuristic error is calculated as follows.Error Heuristic solutionOptimal solutionOptimal solution:The results of the heuristic methods were compared with the results of the optimal solutions obtained by theinteger model, and the errors of these heuristics are given in Fig. 1. As seen from this Fig. 1, the tabu search-IVgives fairly good results in terms of error and it is quite eective in this bicriteria problem.The results of the large size problems (100 6 n 6 1000) were also computed using heuristic methods. Sincethe optimal results of these problems have not been known, the results of the heuristics were compared withthe best result in order to dene their performances. In this comparison, the error, formulated below, was usedas a performance measure:Error Heuristic solution Best heuristic solutionBest heuristic solutionFig. 2 presents, the solution qualities of heuristics according to the weight values. The tabu search-IV gives thebest results of the problem for all weight values.Parameters Alternatives ValuesNumbProcesT. Eren, E. Guner / Applied Mathematics and Computation 183 (2006) 12921300 12991002003004005006007008009001000number of job (n)0100002000030000CPUtime(sn) randomTabu-ITabu-IITabu-IIITabu-IV40000Setup time (sji) 4 U[0,9] U[0,24] U[0,49] U[0,99]Due date (dj) 1 dj sjk Pnj1pj un 1pjWeights (a,b,c) 3 (0.25,0.75); (0.50,0.50); (0.75,0.25)Number of solved problems 10Total problem 10 1 4 1 3 10 = 1200er of job 10 100,200, . . . , 1000sing time (pji) 1 U[1,100]Table 4Experimental set for large problemsFig. 3. The average CPU times of heuristics (100 6 n 6 1000).1300 T. Eren, E. Guner / Applied Mathematics and Computation 183 (2006) 12921300The experimental set of the large size problems is given in Table 4. As seen in Table 4, totally 1200 problemswere solved.The execution times of heuristics for small size problems were so small that they were neglected. However,the average execution times of the heuristics for large size problems can not be neglected as shown in Fig. 3. Itis clear from this Fig. 3 that the longest execution times belong to the random search, Tabu II follows it.6. ConclusionIn this paper, we consider the bicriteria owshop scheduling problem with the weighted sum of total com-pletion time and total tardiness the consideration of the separate setup times. The proposed integer program-ming model can solved the problems up to 20 jobs. The base of this model is structured on Su and Chou [20]sinteger programming model. To solve the large sizes problems up to 1000 jobs, a random search and tabusearch based heuristics methods were used. The performances of heuristics about the solution error were eval-uated with the integer model results for small size problems and each other for large size problems. Totally 720small size problems and 1200 large size problems were solved. According to results, the tabu search IV heu-ristic for all weight values was the more eective than others.In scheduling the multi-machine or multicriteria cases under the sequence-dependent setup times can bealso interesting issues for future studies.References[1] D.R. Sule, K.Y. Huang, Sequency on two and three machines with setup, processing and removal times separated, InternationalJournal of Production Research 21 (1983) 723732.[2] T. Yoshida, K. Hitomi, Optimal two-stage production scheduling with setup times separated, AIIE Transactions 11 (1979) 261263.[3] P. Dileepan, T. Sen, Job lateness in a two-machine owshop with setup times separated, Computers and Operations Research 18(1991) 549556.[4] R. Logendran, C. Sriskandarajah, Two-machine group scheduling problem with blocking and anticipatory setups, European Journalof Operational Research 69 (1993) 467481.[5] A. Allahverdi, Two-stage production scheduling with separated set-up times and stochastic breakdowns, Journal of the OperationalResearch Society 46 (1995) 896904.[6] A. Allahverdi, Scheduling in stochastic owshops with independent setup, processing and removal times, Computers and OperationsResearch 24 (1997) 955960.[7] A. Allahverdi, T. Aldowaisan, Job lateness in owshops with setup and removal times separated, Journal of the Operational ResearchSociety 49 (1998) 10011006.[8] A. Allahverdi, J.N.D. Gupta, T. Aldowaisan, A review of scheduling research involving setup considerations, Omega 27 (1999) 219239.[9] T.C.E. Cheng, J.N.D. Gupta, G. Wang, A review of owshop scheduling research with setup times, Production and OperationsManagement 9 (3) (2000) 262282.[10] T. Eren, The solution approaches for multicriteria owshop scheduling problems, Gazi University Institute of Science andTechnology, Ph.D. Thesis, Ankara, Turkey, 2004.[11] T. Eren, E. Guner, A bicriteria scheduling with sequence-dependent setup times, Applied Mathematics and Computation, in press,doi:10.1016/j.amc.2005.11.112.[12] M.R. Garey, D.S. Johnson, R.R. Sethi, The complexity of owshop and jobshop scheduling, Operations Research 1 (1976) 117129.[13] T. Gonzalez, T. Sen, Flowshop and jobshop schedules: complexity and approximations, Operations Research 26 (1978) 3652.[14] F. Glover, Future paths for integer programming and links to articial intelligence, Computers and Operations Research 5 (1986)533549.[15] S.M. Johnson, Optimal two-and three-stage production schedules with setup times included, Naval Research Logistic Quarterly 1(1954) 6168.[16] M. Nawaz, E.E. Enscore, I. Ham, A heuristic algorithm for the m-machine, n-job ow-shop sequencing problem, Omega 11 (1983)9195.[17] R.L. Fox, Optimization Methods for Engineering Design, Addision Wesley Publishing Company, London, 1971.[18] J.-S.R. Jang, C.T. Sun, E. Mizutani, Neuro-fuzzy and Soft Computing: A Computational Approach to Learning and MachineIntelligence, Prentice Hall, USA, 1997.[19] C. Rajendran, H. Ziegler, Scheduling to minimize the sum of weighted owtime and weighted tardiness of jobs in a owshop withsequence-dependent setup times, European Journal of Operational Research 149 (3) (2003) 513522.[20] L.H. Su, F.-D. Chou, Heuristic for scheduling in a two-machine bicriteria dynamic owshop with setup and processing timesseparated, Production Planning and Control 11 (8) (2000) 806819.A bicriteria flowshop scheduling problem with setup timesIntroductionProblem descriptionThe proposed integer programming modelAssumptionsParametersDecision variablesAuxiliary variablesProposed integer programming modelHeuristic methodsTabu search heuristicRandom searchExperimental resultsConclusionReferences