Study of Objective Functions in Fuzzy Job-Shop Problem

Study of Objective Functions in Fuzzy

Job-Shop Problem

In′e s Gonz′a lez-Rodr′?guez,Camino R.Vela,and Jorge Puente

Dept.of Computer Science,University of Oviedo,Spain

inesgr@uniovi.es,camino@aic.uniovi.es,puente@aic.uniovi.es

Abstract.We consider the fuzzy job-shop problem,a job-shop schedul-

ing problem with uncertain task durations and?exible due-date con-

straints.We propose di?erent de?nitions of the objective function and

analyse solutions obtained for each alternative using a genetic algorithm.

1Introduction

In the last decades,scheduling problems have been subject to intensive research due to their multiple applications in areas of industry,?nance and science[1]. Some of these applications involve modelling the uncertainty and vagueness per-vading real-life situations;this has resulted in a particular branch of scheduling, known as fuzzy scheduling[2],[3].Here we?nd a great variety of approaches, connected with the three semantics of fuzzy sets.They range from represent-ing incomplete or vague states of information to using fuzzy priority rules with linguistic quali?ers or preference modelling.It is also possible to?nd models combining more than one of these approaches.Although the?rst applications of fuzzy scheduling date back to the1970’s,it has not been until recently that it has received an increasing attention.In particular,little work has been done with more realistic and complex problems such as open-shop and job-shop.In classical scheduling,the high complexity of such problems means that practical approaches to solving them usually involve heuristic strategies.Among these, genetic algorithms have proved to be a powerful tool to tackle this kind of prob-lems,due to their ability to cope with huge search spaces involved in optimising schedules[4].All the above motivates our description of a fuzzy job-shop problem and of a genetic algorithm to solve it.

2Description of the Problem

The job shop scheduling problem,also denoted JSSP,consists in scheduling a set of jobs{J1,...,J n}on a set of physical resources or machines{M1,...,M m}, subject to a set of constraints.There are precedence constraints,so each job J i, i=1,...,n,consists of m tasks{θi1,...,θim}to be sequentially scheduled.Also, there are capacity constraints,whereby each taskθij requires the uninterrupted

All authors supported by MCYT-FEDER Grant TIC2003-04153.

L.Rutkowski et al.(Eds.):ICAISC2006,LNAI4029,pp.360–369,2006.

c Springer-Verlag Berlin Heidelberg2006

Study of Objective Functions in Fuzzy Job-Shop Problem361 and exclusive use of one of the machines for its whole processing time.In ad-dition,we may consider due-date constraints,where each job has a maximum completion time and all its tasks must be scheduled to?nish before this time. The goal is twofold:we need to?nd a feasible schedule,so that all constraints hold and then we want this schedule to be optimal,in the sense that its makespan (i.e.,the time it takes to?nish all jobs)is minimal.

2.1Uncertain Processing Times and Flexible Constraints

In real-life applications,it is often the case that the exact duration of a task is not known in advance.For instance,in ship-building processes,some tasks related to piece cutting and welding are performed by a worker and,depending on his/her level of expertise,the task will take a di?erent time to be processed.Hence,it is impossible to know a priori the exact duration of this task.However,based on pre-vious experience,an expert may have some knowledge about the duration,thus being able to estimate,for instance,an interval for the possible processing time or its most typical value.Clearly,classical job shop problems,are not adequate to deal with this type of situations.Instead,it is necessary to somehow model uncertain processing times and thus take advantage of the expert’s knowledge.

It is possible to?nd many examples in the literature where fuzzy numbers are used to represent uncertain processing times.Fuzzy sets proved an alternative to probability distributions,which require a deeper knowledge of the problem and usually yield a complex calculus.When there is little knowledge available, the crudest representation for uncertain processing times would be a human-originated con?dence interval.If some values appear to be more plausible than others,a natural extension is a fuzzy interval or a fuzzy number.The simplest model of fuzzy interval is a triangular fuzzy number or TFN,using only an interval[a1,a3]of possible values and a single plausible value a2in it.That is,for a TFN A,denoted A=(a1,a2,a3),the membership function takes a triangular shape completely determined by the three real numbers,a1≤a2≤a3as follows:

μA(x)=?

???

?

???

?

0:x

x?a1

a2?a1

:a1≤x≤a2

x?a3

a2?a3

:a2

0:a3

(1)

To compute the completion time of a given task,it is necessary to add the task’s duration to its starting time.This can be done using fuzzy number addi-tion,which in the case of TFNs A=(a1,a2,a3)and B=(b1,b2,b3)is reduced to adding three pairs of real numbers as follows:

A+B=(a1+b1,a2+b2,a3+b3)(2) A consequence of this operation is that completion times are TFNs as well.

Another situation where the need of fuzzy number arithmetic arises is when the starting time for a given taskθmust be found.Here,it is necessary to?nd the

362I.Gonz′a lez-Rodr′?guez,C.R.Vela,and J.Puente

maximum between two TFNs,the completion time of the task precedingθin its job J and that precedingθin its resource M.Now,given two TFNs A=(a1,a2,a3)and B=(b1,b2,b3),the maximum A∨B is obtained by extending the lattice operation max on real numbers using the Extension Principle.However,the calculation of the resulting membership function might be quite complex.Also,the result of such an operation,while still being a fuzzy number,is not guaranteed to be a TFN.For these reasons,we approximate A∨B by a TFN,A B,given by:

A∨B≈A B=(a1∨b1,a2∨b2,a3∨b3)(3) The approximation ,proposed in[5]for6-point fuzzy numbers,may coincide with the maximum∨.Even if this is not the case,the support of both fuzzy sets A∨B and A B is exactly the same and the unique point x with full membership in A B also has full membership in A∨B.

Using the addition and the maximum ,it is possible to?nd the comple-tion time for each job.The fuzzy makespan C max would then correspond to the greatest of these TFNs.Unfortunately,neither the maximum∨nor its approx-imation can be used to?nd such TFN,because they do not de?ne a total ordering in the set of TFNs.Instead,it is necessary to use a method for fuzzy number ranking[6].The chosen method consists in obtaining three real numbers C1(A),C2(A),C3(A)from each TFN A as follows:

C1(A)=a1+2a2+a3

4

,(4)

C2(A)=a2,C3(A)=a3?a1

Using real number comparisons,it is then possible to establish a total ordering in any set of TFNs according to Algorithm1.

1:order the TFNs using C1

2:if there are TFNs with identical value of C1then

3:order these TFNs using C2

4:if there are TFNs with identical value of C1and C2then

5:rank them using C3

Algorithm1.Ranking Method for TFNs

In practice,if due-date constraints exist,they are often?exible.For instance, a customer may have a preferred delivery date d1,but some delay will be allowed until a later date d2,after which the order will be cancelled.We would then be completely satis?ed if the job?nishes before d1and after this time our level of satisfaction would decrease,until the job surpasses the later date d2,after which date we will be clearly dissatis?ed.The satisfaction of a due-date constraint becomes a matter of degree,our degree of satisfaction that a job is?nished on a certain date.A common approach to modelling such satisfaction levels is to use a fuzzy set D with linear decreasing membership function:

Study of Objective Functions in Fuzzy Job-Shop Problem363

μD(x)=?

??

??

1:x≤d1

x?d2

d1?d2

:d1

0:d2

(5)

Such membership function expresses a?exible threshold“less than”,represent-ing the satisfaction level sat(t)=μD(t)for the ending date t of the job[2]. However,when dealing with uncertain task durations,the job’s completion time is no longer a real number t,but a TFN C.In this case,the degree to which a completion time C satis?es the due-date constraint D may be measured using the following agreement index[8],[7]:

AI(C,D)=area(D∩C)

area(C)

(6)

The intuition behind this de?nition is to measure the degree to which C is contained in D(the degree of subsethood).

2.2De?nition of the Objective Function

Once we have established a means of modelling uncertain duration times and ?exible due-dates,we can?nd a schedule for a given problem.Let us assume that resource and precedence constraints hold(otherwise,the schedule is un-feasible and hence is not a solution).Every job J i,i=1,...,n has a fuzzy completion time C i;a fuzzy makespan C max may be obtained from these com-pletion times and,in the case that a due date D i exists for job J i,the agree-ment index AI i=AI i(C i,D i)measures to what degree the due date is satis-?ed.Based on this information,it is necessary to decide on the quality of this schedule.

If?exible due-date constraints exist,the degree of feasibility of the given schedule may be obtained by combining the satisfaction degrees AI i,i=1,...,n. If the aim is that due dates be satis?ed in average,the degree to which a schedule s is feasible is given by:

AI av=1

n

n

i=1

AI i(7)

A more restrictive approach is to expect that all due dates be satis?ed,so satis-faction degrees are combined using the minimum aggregation operator as follows:

AI min=min

i=1,...,n

AI i(8) The value of AI av can be seen as the probability Pr(F)of the fuzzy event F“the schedule s is feasible”over the?nite domain of jobs D={J1,...,J n},provided that the membership of job J i in F isμF(J i)=AI i,i=1,...,n.Similarly, AI min corresponds to the necessity measure N(F)of the fuzzy event F over the?nite domain D[9].Clearly,AI av,AI min∈[0,1]and AI min≤AI av.Both measure the degree to which due-date constraints are satis?ed by the schedule,

364I.Gonz′a lez-Rodr′?guez,C.R.Vela,and J.Puente

and our aim should be to maximise them.However,the two measures model di?erent requirements for due dates and encourage di?erent behaviours.

Regarding makespan,the“smaller”C max is,the better the schedule is.Now, because C max is a TFN,it is not totally clear what is meant by“smaller”.If we consider the total ordering de?ned by the ranking method,it would mean a smaller C1(C max)and our goal should be to minimise this quantity.

Given both measures of feasibility and the makespan and depending on the ?nal goal of the job-shop scheduling problem,we may de?ne di?erent objective functions.

If no due-date constraint is considered and the only goal is to?nd a schedule with minimum makespan,the objective function will be given by:

f1=

1

C1(C max)

(9)

When due-date constraints are present and the only goal is to?nd a fea-sible schedule,the objective function of the job-shop problem may be de?ned alternatively as:

f2=AI av f3=AI min(10) Finally,even if due-date constraints hold,we may also want to minimise the makespan.Here,the degree of feasibility,given by AI av or AI min,must be max-imised and,at the same time,the makespan(in fact,C1(C max))must be min-imised.The combination of the two goals yield the following objective functions (depending on the feasibility measure used):

f4=

AI av

C1(C max)

f5=

AI min

C1(C max)

(11)

Having proposed the above objective functions,we may de?ne the Fuzzy Job Shop Scheduling Problem or FJSSP as the problem of maximising f i,i=1, (5)

subject to precedence and capacity constraints.

To our knowledge,despite their simplicity,the above objective functions for the FJSSP have not been yet considered in the literature.For instance,the FJSSP is considered in[10]and[7],but the de?nition of the objective function, based on fuzzy decision making,is completely di?erent.A job-shop problem is also considered[5],but uncertain durations are modelled using6-point fuzzy numbers,there are no due dates,and the only objective of minimising makespan is achieved based on fuzzy number comparison.Finally,similar objective func-tions appear in[8],but in the setting of a di?erent and less complex problem, the fuzzy?ow-shop problem.

3Using Genetic Algorithms to Solve FJSSP

In classical JSSP,the search for an optimal schedule is usually limited to the space of active schedules.One of the best-known algorithms to?nd active sched-ules is the G&T Algorithm[11],which allows to use complementary techniques

Study of Objective Functions in Fuzzy Job-Shop Problem365 1:A={θi1,i=1,...,n};/*?rst task of each job*/

2:while A=?do

3:Find the taskθ ∈A with minimum earliest completion time/*CT(θ)1*/;

4:Let M be the machine required byθ and B the subset of tasks in A requiring machine M ;

5:Delete from B any task that cannot overlap withθ ;/*ST(θ)1>CT(θ )3*/ 6:Selectθ ∈B(according to some criteria)to be scheduled;

7:Removeθ from A and,ifθ is not the last task of its job,insert in A the task followingθ in the job;

Algorithm2.Fuzzy G&T

to reduce the search space[12].Also,it can be used as a basis for e?cient genetic algorithms(GA),successful in solving classical job-shop problems.We describe a possible extension of G&T for the FJSSP(see Algorithm2)and a GA to solve the FJSSP based on this algorithm.Both algorithms were?rst proposed for a di?erent objective function that also needed to be maximised in[10]and were inspired in the work from[7].

Chromosomes are a direct codi?cation of schedules.If there are n jobs and m machines,each individual will be represented by a n×m matrix,where element (i,j)represents the completion time for the task in job J i requiring resource M j.Therefore,each row is the schedule of a job’s tasks over the corresponding resources.Each chromosome in the initial population for the GA can be gener-ated with fuzzy G&T algorithm,choosing a task at random from the con?ict set B.To prevent premature convergence,it is advisable that the initial pop-ulation be diverse enough.Hence,a new individual will only be incorporated to the population if similarity to other members of the population is less than a given thresholdσ.Let P r I(θ)be the set of tasks precedingθin its machine according to the ordering induced by individual I and let Su I(θ)be the set of tasks followingθin its machine w.r.t.the same ordering.Then,the similarity between two individuals I1and I2is de?ned using phenotype distance as follows:

Sim(I1,I2)= n

i=1

m

j=1

(|P r I

1∩I2

(θij)|+|Su I

1∩I2

(θij)|)

n·m·(m?1)

(12)

where|P r I

1∩I2(θij)|denotes the cardinal of P r I

1

(θij)∩P r I

2

(θij)and|Su I

1∩I2

(θij)|denotes de cardinal of Su I

1(θij)∩Su I

2

(θij).

The value of the?tness function for a chromosome is simply the value of the objective function for the corresponding schedule.

The crossover operator,applied with probability p m,consists in performing the fuzzy G&T algorithm and solve non-determinism situations using the in-formation from the parents.Every time the con?ict set B has more than one element,the selected task is that with earliest completion time in the parents, according to the ranking algorithm.The mutation operator is embedded in the crossover operator,so that,with a given probability p m,the task from the con-?ict set is selected at random.

366I.Gonz′a lez-Rodr′?guez,C.R.Vela,and J.Puente

1:Generate initial population divided in k groups P1,...,P k containing K individuals each;

2:while terminating condition T1is not satis?ed do

3:for i=1;i≤k;i++do

4:repeat

5:select2parents at random from P i;

6:obtain3children by crossover and mutation;

7:select the best of3children and the best of remaining children and parents for the new population NP i;

8:until a new population NP i is complete

9:Replace the worst individual in NP i with the best of P i.

10:Merge P1,...,P k into a single population P;

11:while Terminating condition T2is not satis?ed do

12:Obtain a new population from P following the scheme above;

Algorithm3.Genetic Algorithm for FJSSP

The general scheme of the GA,in Algorithm3,is designed to avoid prema-ture convergence to local optima by using a niche-based system.The population is initially divided in k sub-populations,containing K individuals each.This is more feasible,from a computational point of view,than generating a sin-gle initial population.Each sub-population evolves separately,until a certain convergence is obtained(in practice,for I min generations).At this stage,these sub-populations are merged into a single population of N individuals,which will again evolve until some terminating condition holds(in practice,when a total of I max generations is reached).

4Experimental Results

Unfortunately,benchmark examples of FJSSP in the literature are scarce,clearly a problem for any thorough experimentation,where a su?ciently large and di-verse set of problems is needed.For this reason,we propose a novel heuristic method to generate new problems.It will later be used to provide a sample of problems to test the di?erent objective functions introduced in Section2.

4.1Generation of New Problems

In order to de?ne a problem of size n×m,where n is the number of jobs and m is the number of resources,the following must be de?ned:capacity constraints, assigning a machine to each task of every job,uncertain durations,in the form of TFNs,and?exible due-dates.Here,we have generated new problems(ten problems of size10×10and ten problems of size20×5)using the following heuristic method.For a problem of size n×m,capacity constraints are de?ned by a matrix R of size n×m where row i is a random permutation of(1,...,m) representing the machine assignments in job J i.Regarding the duration of a given task,its most typical value a2is obtained at random from the interval

Study of Objective Functions in Fuzzy Job-Shop Problem 367

Table 1.Average results obtained with di?erent objective functions.Parameter values are:p m =0.03,p c =0.9,σ=0.8and N /I min /I max are 200/100/200,except for 6×6,where they are 100/50/100.

Problems objective function

AI av AI min C 1(C max )f 1

0.6780.09798.700f 2

0.8880.545115.960S&K f 3

0.8560.700119.133f 4

0.8710.525105.192f 5

0.8540.676110.485f

0.8110.444106.346f 1

0.9480.662870.591f 2

1.0000.997966.03210×10f 3

1.0000.999964.852f 4

0.9940.948883.685f 5

0.9990.994903.654f

0.9960.966936.173f 1

0.7370.0161174.879f 2

0.9530.5051251.99120×5

f 3

0.8770.6191237.380f 4

0.9340.3591193.927f 5

0.8740.6191220.791f 0.6950.0821273.926[1,99]and a 1and a 3are random values from [int (23a 2),a 2]and [a 2,int (43a 2)]

respectively,where int (x )denotes the closest integer to a given real number x .Due-date values are the most di?cult to de?ne.If they are too strict,the problem will have no solution and if they are too lenient,due-date constraints will always be satis?ed,which is equivalent to having no constraints at all.For a given job J i ,let ιi = m j =1a 2i,j be the sum of most typical durations across all its tasks.Also,for a given task θi,j let ρi,j be the sum of most typical durations of all other tasks requiring the same machine as θi,j ,ρi,j = θi,j =θ:M (θ)=M (θi,j )a 2(θ),where M (θ)denotes the machine required by task θand a 2(θ)denotes its most typical duration.Finally,let ρi =max j =1,...,m ρi,j be the maximum of such values across all tasks in job J i .Then,the earlier due-date d 1is taken as a random value from [d m ,d M ],where d m =ιi +0.5ρi and d M =ιi +ρi .The later due-date d 2is a random value from [d 1,int (1.1d 1)].

4.2Results of the GA with Di?erent Objective Functions

In addition to the 20new problems,we consider the problems proposed in [7],three of size 6×6and three of size 10×10,denoted S&K.For all 26problems,we have run the GA using the ?ve objective functions proposed in Section 2and the objective function based on fuzzy decision making proposed in [10](denoted f hereafter).For each problem and objective function,the GA from Section 3is ex-ecuted 20times with the parameter values used in [10](p m /p c /σ/N /I min /I max

368I.Gonz′a lez-Rodr′?guez,C.R.Vela,and J.Puente

a)Cmax(lower is better)b)AImin(higher is better)

Fig.1.Results for problems of size20×5using di?erent objective functions equal to0.03/0.9/0.8/200/100/200).For the obtained schedule,we measure AI av,AI min and C1(C max).Table1is a summary of the obtained results,with average values across all problems in a family.Notice that for problems of size 10×10,due dates that are in general easy to satisfy,whilst for problems of size 20×5due dates are quite strict in some jobs.Let us now see if the results support the arguments used to de?ne the di?erent objective functions in Section2.As expected when the objective functions were introduced,the results indicate that, when only the productivity goal of minimising C max is considered,f1should be used.Notice that,in accordance with what has just been said,the lowest values of C max are obtained with schedules for which at least a due-date restriction is not satis?ed at all.

More surprising are the results with respect to due-date satisfaction.At?rst, we may feel tempted to conclude that,if the goal is to respect delivery dates in average,then f2should be used and,if the goal is to respect all delivery dates, then f3should be used.This would certainly correspond to the motivation for de?ning f2and f3.However,a more careful look shows that if we use f4and f5 instead,due dates are satis?ed to almost the same degree and there is the added bene?t of reducing the makespan and improving in productivity.Therefore,if the goal is to satisfy due dates,it seems preferable to use the more complex objective functions f4or f5,instead of just using f2or f3.Notice as well that using AI av as objective function does not always provide high values for AI min.Finally, if the goal consists in both maximising due-date satisfaction and minimising makespan,the results suggest that the objective function should be f5.For all26problems,AI av values are similar with both f4and f5,whilst AI min does improve considerably when f5is used.Regarding C1(C max),f4does obtain better schedules,but the di?erence does not compensate the loss of due-date satisfaction in AI min.This is further illustrated by Figure1.In any case,the

objective function f,de?ned in[10]to simultaneously maximise1

C1(C max),AI av

and AI min,obtains worse results than either f4or f5.We may conclude then that overall it is preferable to use the simpler objective function f5,proposed herein.

Study of Objective Functions in Fuzzy Job-Shop Problem369 5Conclusions and Future Work

We have considered the FJSSP,a version of JSSP that tries to model the impre-cise nature of data in real-world problems,using fuzzy sets to represent uncertain processing times and considering?exible due-dates.Di?erent objective functions have been proposed,depending on whether the aim is to optimise productivity or respect delivery dates,and their behaviour has been compared based on the results obtained using a GA.We have seen that,overall,it is preferable to use the function denoted f5.This also obtains better results than the function from [10]and has the further advantage that its de?nition involves no parameters. References

1.Brucker,P.:Scheduling Algorithms.4th edn.Springer(2004)

2.Dubois,D.,Fargier,H.,Fortemps,P.:Fuzzy scheduling:Modelling?exible con-

straints vs.coping with incomplete knowledge.European Journal of Operational Research147(2003)231–252

3.S l owi′n ski,R.,Hapke,M.,eds.:Scheduling Under Fuzziness.Volume37of Studies

in Fuzziness and Soft Computing.Physica-Verlag(2000)

4.Bierwirth,C.,Mattfeld,D.C.:Production scheduling and rescheduling with genetic

algorithms.Evolutionary Computation7(1999)1–17

5.Fortemps,P.:Jobshop scheduling with imprecise durations:a fuzzy approach.

IEEE Transactions of Fuzzy Systems7(1997)557–569

6.Bortolan,G.,Degani,R.:A review of some methods for ranking fuzzy subsets.

In Dubois,D.,Prade,H.,Yager,R.,eds.:Readings in Fuzzy Sets for Intelligence Systems.Morgan Kaufmann(1993)149–158

7.Sakawa,M.,Kubota,R.:Fuzzy programming for multiobjective job shop schedul-

ing with fuzzy processing time and fuzzy duedate through genetic algorithms.Eu-ropean Journal of Operational Research120(2000)393–407

8.Celano,G.,Costa,A.,Fichera,S.:An evolutionary algorithm for pure fuzzy?ow-

shop scheduling problems.International Journal of Uncertainty,Fuzziness and Knowledge-Based Systems11(2003)655–669

9.Dubois,D.,Prade,H.:A review of fuzzy set aggregation https://www.doczj.com/doc/2e8193961.html,rmation

Sciences36(1985)85–121

10.Gonz′a lez Rodr′?guez,I.,Vela,C.R.,Puente,J.:An evolutionary approach to de-

signing and solving fuzzy job-shop problems.Lecture Notes in Computer Science 3562(2005)74–83

11.Gi?er,B.,Thomson,G.L.:Algorithms for solving production scheduling problems.

Operations Research8(1960)487–503

12.Varela,R.,Vela,C.R.,Puente,J.,G′o mez,A.:A knowledge-based evolutionary

strategy for scheduling problems with bottlenecks.European Journal of Opera-tional Research145(2003)57–71