In this paper, we consider job shop scheduling and machine location problem, simultaneously. Processing, transportation, and setup times are defined as deterministic parameters. The purpose of this paper is to determine machine location and job scheduling such that the make span and transportation cost is minimized. Therefore, the proposed model is a multi-objective problem one, where the first objective function minimizes make span and another minimizes the transportation cost. To solve the multi-objective problem, two methods are evaluated. Considering combination of job shop scheduling problem and machine location problem makes the proposed model more complex than job shop scheduling problem, which is an NP-hard problem. Therefore, to solve the proposed model, genetic algorithm as a meta-heuristic algorithm is implemented. To show the efficiency of the proposed genetic algorithm, 6×6 job shop scheduling problems are considered.

Kazemi, M., Poormoaied, S & Eslami, G. (2012). Optimizing combination of job shop scheduling and quadratic assignment problem through multi-objective decision making approach.Management Science Letters, 2(6), 2011-2018.

Management Science Letters 2 (2012) 2011–2018

Contents lists available at GrowingScience

Management Science Letters

homepage: www.GrowingScience.com/msl

Optimizing combination of job shop scheduling and quadratic assignment problem through multi-objective decision making approach

Mostafa Kazemi, Saeed Poormoaied* and Ghasem Eslami

Department of Economic and Aministrative Science, Ferdowsi University of Mashhad, Iran

Department of industrial engineering, Ferdowsi University of Mashhad, Iran

A R T I C L E I N F O A B S T R A C T

Article history:

Received April 17, 2012

Accepted 11 June 2012

Available online

June 14 2012 In this paper, we consider job shop scheduling and machine location problem, simultaneously. Processing, transportation, and setup times are defined as deterministic parameters. The purpose of this paper is to determine machine location and job scheduling such that the make span and transportation cost is minimized. Therefore, the proposed model is a multi-objective problem one, where the first objective function minimizes make span and another minimizes the transportation cost. To solve the multi-objective problem, two methods are evaluated. Considering combination of job shop scheduling problem and machine location problem makes the proposed model more complex than job shop scheduling problem, which is an NP-hard problem. Therefore, to solve the proposed model, genetic algorithm as a meta-heuristic algorithm is implemented. To show the efficiency of the proposed genetic algorithm, 6×6 job shop scheduling problems are considered.

© 2012 Growing Science Ltd. All rights reserved.

Keywords:

Job shop scheduling

Quadratic assignment problem Multi-objective problem 1. Introduction

Job shop scheduling problem (JSSP) is an important problem for the production planning because JSSP has many real-world applications. The aim of JSSP is to specify the job-sequencing on machines so that criteria performances such as make span, tardiness or earliness penalty are minimized. JSSP is important in terms of production management and combinational optimization and it has attracted a number of new researchers so far. In this paper, we investigate combination of Job shop scheduling problem and machine location problem in by MODM approach. The location of machine affects on transportation time among different machines. In addition, because of common parameters such as processing and setup times, transportation time is also considered and these three parameters are assumed to be deterministic.

In literature of scheduling, job shop scheduling problem and machine location problem were studied, separately. In other word, to the best of our knowledge, there is no research, which investigates these two problems by multi objective decision making (MODM) approach. However, in the following, we review the researches on job shop scheduling problem and machine location problem.

JSSP has introduced as criteria for evaluation of new optimization approach since 1960. Since then, many papers about JSSP have been published and a lot of methods for solving JSSP have been introduced. One of the most successful methods was shifting bottleneck method proposed by Sule (1997), but an effective algorithm, which can solve JSSP in polynomial time have never been introduced. In other words, problems with 10 machines and 10 jobs was not solved for one forth century until 1986 and in the present problems with 20 machines and 20 jobs has not yet been solved. Many researchers who deal with JSSP assumed that time parameters such as processing time; setup time and transportation time are fixed and deterministic (Jackson, 1956; Li et al., 2010; Lawrence, 1993; Niu et al., 2008; Huang, 2010; Satake et al., 1994).

Transportation cost is most portion of the operational costs, so optimal location can decrease this cost and can affect cheap production in competitive world. It is the most important reason that persuades researchers to take attention it. Assignment problem (AP) is one of the most applicable problems in both manufacturing and service systems that by applying it we can assign n jobs to n workers so that total assignment costs is minimized. Chou et al. (2008) solved the location problem by multi-criteria decision making (MCDM) approach.

From the literature above, we can conclude that this paper considers two classes of problems, simultaneously; problem 1 deals with JSSP in which we decide to minimize make span and problem 2 deals with QAP in which we decide to minimize assignment cost. Therefore, the proposed model is an MODM and to solve the problem, we use the MODM based approaches. Some studies considered the MODM problem are Charnes and Cooper (1961), Keeney and Raiffa (1993) and Zeleny et al. (2001) where they considered the job shop scheduling with two objectives and dealt with this problem in fuzzy environment through genetic algorithm (GA). Literature view shows that no studies have considered the combination of JSSP and QAP with MODM approach. Therefore, in this paper we deal with this problem and organize our papers as follows:

In Section 2, we define the problem. Then, the mathematical formulation of the proposed model is presented in Section 3. The proposed approach for solving the multi-objective problem is described in Section 4. In section 5, GA is explained. In Section 6, we present a numerical example. Finally, the last section deals with concluding remarks and suggestions for further researches.

2. Problem definition

There are n jobs and each job needs a series of operations denoted by Ai. The operation sequencing on each job is pre-specified. We have m machines and there are m locations for locating machines. Before the beginning the process, we assume that all jobs are in the depot. The location of depot is known and fixed. The aim of proposed model is to determine job scheduling and the location of machines, simultaneously so that the make span and transportation cost is minimized.

2.1. Problem assumptions

The problem assumptions are as follows:

1- Each machine processes just one operation.

2- Each machine processes one job at a time.

3- Each machine can be located in each location.

4- Preemption is not allowable.

5- Scheduling considered in this paper is Non-Anticipatory Scheduling Problem.

2.2. Notations

The notations used in the problem modeling are:

Parameters

n: Number of jobs.

m: Number of machines.

fkl: Job flow between machine k and l.

Drs: Distance between location r and s.

Crskl: Transportation cost between location r and s which machine k and l are located in these locations. Crskl is equal to fkl×Drs×wPKi: Processing time of job i on machine k.

trs: Transportation time between location r and s.

Sijk: Set up time job i to j in machine k.

ilast: Last operation of job i.

yki: Starting time of job i on machine k.

(As each machine processes just one operation, the number of operations is the same as the number of machines. Therefore, the index of operation demonstrates the machine index and vice versa.)

Ci: Completion time of job i; Ci=yi last, i+Pi last, i Cki: Finishing time of job i on machine k.

Decision variables

Zkr: If machine k is assigned to location r, zkr is equal 1 otherwise 0.

Xkij: If job i is operated earlier than job j on machine k, Xkij is equal 1 otherwise 0.

3. Modeling

The objective function and constraints of the proposed model can be formulated as model 1:

Model 1:

ming1=k=0ml=0k≠lms=0mr=0s≠rr<smCrsklZkrZlsming2=CmaxSubject to:

(1) Cmax≥Ci last, i ; i=0,1,…,n(2) k=0mZkr=1 ; r=0,1,….,m(3) r=0mZkr=1 ; k=0,1,….,m∀ k,i→l,i∈ Ai ; i=1,…,m and k,l,r,s=0,1,….,m ;r≠s , r<s ,l≠k :

(4) yli≥yki+Pki+trs-M1-Zkr+(1-Zls)(5) ykj≥yki+Pki+Sijk-M1-Xkij ; ∀K,i,K,j ; k=1,…,m ; i, j=0,1,…,n(6) yki≥ykj+Pkj+Sjik-M Xkij ; ∀K,i,K,j ; k=1,…,m ; i, j=0,1,…,n(7) Z00=1(8) y0i=0 ; i=1,…,n(9) yij∈R+ ; i,j=1,…,n(10) Zkr∈0,1 ; k,r=0,1,….,m(11) Xkij∈0,1 ; ∀K,i,K,j ; k=1,….,m ; i, j=0,1,…,nIn Eq (4), (5), (6), M is a positive big number. In this model, we have two objective functions formulated as minCmax and mink=0ml=0k≠lms=0mr=0s≠rr<smCrsklZkrZls, respectively. Eq. (1) states that completion time of job i is greater than or equal to completion time of job i on the last machine in Ai. Eq. (2) expresses that each location is assigned to one machine. Eq. (3) expresses that each machine is assigned to one location. Eq. (4) expresses that if job i is to be processed on machine k before machine l, starting time of job i on machine l is more than starting time of this job on machine k plus its processing time on machine k and transportation time between machine k and l. Eq. (5) and (6) express that two jobs cannot be processed on one machine simultaneously, i.e. each machine processes one job at a time. Eq. (7) guarantees that the location of depot is fixed. Eq. (8) expresses that at first all jobs are in depot (number 0 for machine index and location index refers to depot).

4. Solving method

As stated before, the proposed model is a multi-objective problem. So, to solve the problem, we need to use MODM approaches. In section 4-1 and 4-2, we propose two MODM methods and in the following these methods will be compared.

4.1. Approach 1

Consider the general MODM problem as follows:

max f1x,f2x,…,fn(x)min g1x,g2x,…,gm(x)subject to x∈X

where X represents the feasible solution. Firstly, we assume that each objective is optimized separately as follows:

fi*= max fix (i=1,…,n) gi*= min gix (i=1,…,n)

subject to : x ϵ X subject to : x ϵ Xnd assume that β is a real number in interval [0, 1]. Considering these assumptions, we can convert the MODM problem into single objective problem as follows:

max βsubject to β≤fixfi* i=1,…,n

β≤gi*gix i=1,…,m x ϵ XUsing the above proposed model, we can rewrite model 1 as follows:

max βsubject to:

β≤g1*k=0mi=0ms=0mr=0mCrskl ZkrZls ; i=1,…,nβ≤g2*Cmax ; i=1,…,nCmax≥Cilast , i ; i=1,…,n0≤β≤1Eqs. (1-11)

4.2. Approach 2

This method is known as L-P metric. Again, consider the general MODM problem as follows:

max f1x,f2x,…,fn(x)min g1x,g2x,…,gm(x)subject to x ∈Xwhere X represents the feasible solution. First, we assume that each objective is optimized separately as follows:

fi*= max fix ; (i=1,…,n) gi*= min gix ; (i=1,…,m)

subject to x ϵ X subject to x ϵ XWe can use the L-P metric approach as follows:

L-P=δ1i=1nfi*-fi(x)fi*p+δ2i=1mgix-gi*gi*p1pIf set P = 2, the objective function will be as follows (L-2 metric):

L-2=δ1i=1nfi*-fi(x)fi*2+δ2i=1mgix-gi*gi*212Setting δ1=0.5 and δ2=0.5, the objective function will be as follows:

min0.5×i=1nk=0mi=0ms=0mr=0mCrskl ZkrZls-g1*k≠l ,s≠r,r<sg1*2+0.5×i=1mCmax-g2*g2*212subject to:

Eqs. (1-11)

In section 6, we compare these approaches by presenting a numerical example and show which approach is more efficient.

5. Genetic algorithm

The GA used in this research paper is similar to the ones used by Park (2007). This is known as a simple genetic algorithm. In the following, we briefly describe this method. In this method, they developed an efficient scheduling method based on genetic algorithm to address JSSP. They also design a scheduling method based on Single Genetic Algorithm (SGA) and Parallel Genetic Algorithm (PGA). In the scheduling method, the representation, encoding the job number, was made to be always feasible, the initial population was generated through integrating representation and G&T algorithm, the new genetic operators and selection method were designed to better transmit the temporal relationships in the chromosome, and island model PGA were proposed.

Finally, we summarize our genetic algorithm proposed in this paper in Fig. 1.

Begin

n: number of jobs;

m: number of machine;

crossoverP: percentage of Crossover;

mutationP: percentage of Mutation;

populationSize: number of chromosomes;

maxGeneration: number of generations;

population ← Create first population;

generation ←1;

While generation < MaxGeneration do

Evaluate( poulatoin);

If Best_Fitness_in_Genaration>Best_Fitness then

Best_Fitness = Best_Fitness_in_generation;

Best_Completion_Time = Best_Completion_Time_in_generation;

End If.

P ← a ranodom number between 0 and 1;

If crossoverP>P then

Crossover (population);

End if.

If mutationP >P then

Mutation (population);

End if.

generation = generation+1;

End While.

Return Best_completio_time;

End.

Evaluate procedure:

Begin

For i: 1 to populationSize

Decode chromosome number i;

Calculate completion_time of each job;

Calaculate chromosome_Fitness based on completion_time;

If Chromosome_Fitness> Best_Fitness_in_Generation then

Best_Fitness_in_Generation = Choromosome_Fitness;

Best_Completion_Time_in_generation = completion_time

End if.

End.



Fig. 1. Pseudo code for the proposed model

6. Numerical example

Consider three jobs are supposed to be processed on three machines. The location of these machines is pre-specified. At first, all jobs are in the depot. The aim is to assign each machine to one location and determine the job sequence on each machine such that two objectives including make span and transportation cost is minimized. The operation of each job is as follows:







Table 1

Transportation time between location r and s (trs) – (unit of time)

Location 3 Location 2 Location 1 Location 0 5 3 2 0 Location 0

4 6 0 2 Location 1

3 0 6 3 Location 2

0 3 4 5 Location 3

Table 2 Table 3

Set-up time from job i to j on machine 1 (Sij1) Set-up time from job i to j on machine 2 (Sij2)

Job 3 Job 2 Job 1 i Job 3 Job 2 Job 1 i

1 2 0 Job 1 3 2 0 Job 1

3 0 2 Job 2 1 0 3 Job 2

0 1 3 Job 3 0 3 2 Job 3

Table 4 Table 5

Set-up time from job i to j on machine 3 (Sij3) Set-up time of each job on each machine (S0jk)

Machine 3 Machine 2 Machine 1 i Job 3 Job 2 Job 1 i

2 2 0 Job 1 3 2 0 Job 1

3 0 2 Job 2 2 0 3 Job 2

0 1 3 Job 3 0 1 3 Job 3



Table 7 Table 8

Distance between location r and s (Drs) Material flow between two machines (fkl)

Mach. 3 Mach. 2 Mach. 1 Mach. 0 k Mach. 3 Mach. 2 Mach. 1 Mach. 0 r

5 4 7 0 Mach. 0 3 6 3 0 Location 0

9 8 0 7 Mach. 1 4 4 0 3 Location 1

7 0 8 4 Mach. 2 5 0 4 6 Location 2

0 7 9 5 Mach. 3 0 5 4 3 Location 3



Numerical result shows that the result obtained from method 2 is better. So, method 2 is more efficient that method 1. The following results have been obtained from 20 randomly generated problem instances.

Result obtained from method 1

M1 in P2, M2 in P3, and M3 in P1

Job sequencing Machine 1 Machine 2 Machine 3

1 – 2 – 3 3 – 1 – 2 2 – 1 – 3

Transportation cost: 310,000 $ Completion time: 31

Result obtained from method 2

M1 in P3, M2 in P1, and M3 in P2

Job sequencing Machine 1 Machine 2 Machine 3

2 – 3 – 1 3 – 2 – 1 2 – 1 – 3

Transportation cost: 290,000 $ Completion time: 28

7. Conclusions

In this study, combination of job shop scheduling and quadratic assignment problem has been considered. The proposed model contains two objective functions; the first one is to minimize the transportation cost and the second one is to minimize the make span. The aim of this paper is to determine the location of machines and the job sequencing, simultaneously such that two objectives stated before is minimized. As the proposed model is a multi-objective problem, to solve the model, we use two MODM approach. Computational result shows that L-P metric is an efficient method for solving the proposed model. The following are some proposals which remain open for future study. Considering the problem in open shop or flow shop is a good idea as well as solving the problem through other meta-heuristic algorithms can be considered.

Reference

Charnes, A., & Cooper W.W. (1961). Management models and industrial applications of linear programming. 1st ed., John Willey, New York.

Chou, T.Y., Hsu, C.L., Chen, M.C. (2008). A fuzzy multi criteria decision model for international tourist hotels location selection. International Journal of Hospitality Management, 27, 293–301.

Fisher H., & Thompson G. L. (1973). Probabilistic learning combinations of local job-shop scheduling rules. In Industrial Scheduling: NJ, Prentice Hall, 128-139.

Huang, R.H. (2010). Multi-objective job-shop scheduling with lot-splitting production. International Journal of Production Economics, 124, 206–213.

Keeney R.L., & Raiffa H. (1993). Decision with multiple objectives. Cambridge university press, Cambridge.

Jackson, J. R. J. (1956). An extension of Johnson’s results on job lot scheduling. Navel Research Logistics Quarterly, 3, 201-203.

Lawrence S. (1993). Resource constraint project scheduling. An experimental investigation ofhueristic scheduling techniques. Carnegie-Mellon University, 412-435.

Li, J.Q., Pan, Q.K., & Liang, Y.C. (2010). An effective hybrid tabu search algorithm for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 59, 647–662.

Niu, Q., Jiao, B., & Xingsheng, G. (2008). Particle swarm optimization combined with genetic operators for job shop scheduling problem with fuzzy processing time. Applied Mathematics and Computation, 205, 148–158.

Park, B.J., Choi, H.R., & Kang, M.H. (2007). Multi-agent Based Integration of Production and Distribution Planning Using Genetic Algorithm in the Supply Chain Management. Advances in Soft Computing, 41, 969-706.

Sule., D.R. (1997). Industrial Scheduling, PWS Publishing Company. 37-49.

Satake T., Morikawa K., & Nakamura N. (1994). Neural network approach for minimizing the make span of the general job shop. International Journal of Production Economics, 33, 67-74.

Sakawa, M., & Kubota, R. (2001). Two-objective fuzzy job shop scheduling through genetic algorithms. Electronics and Communications in Japan, 84 (4), 60-67.

Zeleny, M. (1973). Compromise Programming. Multiple Criteria Decision Making, 262-301.