Keywords

1 Introduction

Over the past decades, intensive researches have been conducted aiming at various applications of job shop scheduling problem (JSSP), for instance production planning and control. The typical assumption of JSSP is: there are a set of N jobs and a set of M machines or work nodes. Each job consists of a specific operation set which expresses a distinct processing route that has already been fixed and known in advance. All machines are available at time zero, and preemption is forbidden in work process. Most of all, the processing time of each operation has been given clearly. However, owing to the time-based-competition, the impact of uncertain factors cannot be ignored [1]. The conventional JSSP is not suitable in many cases due to various kinds of vagueness existing in real-world scheduling problems [2]. To meet the requirements of applications, many theses have applied the JSSP in uncertain environment, i.e., fuzzy job shop scheduling problem (FJSSP) [3].

The conventional optimization objectives of JSSP is to reduce tardiness (or Make span) or maximize the utilization of each machine [4, 5]. Generally speaking, many objectives are conflicting, which means it is impossible to optimize all the objectives. Bilkay and others [6] had ever proposed a delay cost concept during the decision-making to minimize the total penalty for the completion delay of the operations, which is one of the most important objectives. Sakawa and Kubota [7] provided a multi-objective FJSSP with fuzzy processing time, which is to maximize the agreement index (AI) and optimize the maximum fuzzy completion time.

In current research, stochastic method and fuzzy set theory are proposed to handle imprecise variables in FJSSP. Sakawa and Mori [8] have developed a novel concept of similarity among individuals, which is an effective solution to measure fuzzy parameters. Meanwhile, Lei [3], Canbolat and Gundogar [9] have established kinds of membership functions (e.g. triangle, trapezoid, and rectangle membership functions) to represent uncertain processing time. Furthermore, Wu and others [10] had applied the fuzzy ranking method and fuzzy procedure into FJSSP to compare the priority of fuzzy variables, which is an effective method to yield scheduling planning.

In this research, interval numbers are adopted to represent fuzzy parameters and a novel ranking method towards interval numbers is proposed. After that, we analyze the constraint conditions of FJJSP and convert it into constraint satisfaction problem with the maximum AI as an optimization objective. The IPSO algorithm is used to yield solutions and the experiment results have proved a good performance of the proposed algorithm.

2 Problems and Formulation

2.1 Interval Number Theory

Definition 1

[11] We use R to denote a real number set, and for any \( a_{i}^{ - } ,a_{i}^{ + } \in R \) we refer to the close interval \( a_{i} = \left[ {a_{i}^{ - } ,a_{i}^{ + } } \right] \) as an interval number when \( a_{i}^{ - } \le a_{i}^{ + } \). Especially in case of \( a_{i}^{ - } = a_{i}^{ + } \), a i is degenerated as a real number.

By Definition 1, for a discrete interval number a i , the point values of \( a_{i}^{ - } \) and \( a_{i}^{ + } \) must be known exactly. Generally speaking, the actual value of a i is a real number in the close interval \( [a_{i}^{ - } ,a_{i}^{ + } ] \), and subject to a special probability distribution (or a membership function).

Definition 2

Suppose X is the actual value of a i , and \( x \) is a discrete variable in \( \left[ {a_{i}^{ - } ,a_{i}^{ + } } \right] \). Then the probability of X ≤ x is \( F_{i} \left( x \right) = \int_{{a_{i}^{ - } }}^{x} {f_{i} (X)dX} \), where F i (x) and f i (x) are referred to as the probability distribution function and probability density function respectively.

At present, conventional ranking methods only suitable for interval numbers of special types, for instance, triangle interval number, uniform interval number, and trapezoid interval number [12]. Therefore, the definition of fuzzy binary ordering relation is proposed to determine the priority of any fuzzy variables.

Definition 3

Suppose ‘\( \prec \)’, ‘\( \succ \)’ and ‘\( = \)’ are the fuzzy binary ordering relations for a nonempty interval number set \( I \), and they are referred to as partial order in case the following conditions are satisfied:

  1. (1)

    Reflexivity: a i  = a i , \( \forall \) a i  \( \in \) I;

  2. (2)

    Antisymmetry: If a j  \( \succ \) a i , then a i  \( \prec \) a j , \( \forall \) a i , a j  \( \in \) I;

  3. (3)

    Transitivity: If a i  \( \prec \) a j and a j  \( \prec \) a k , then a i  \( \prec \) a k , \( \forall \) a i , a j , a k \( \in \) I.

Definition 4

If a i and a j have been related to probability density functions f i (x) and f j (x) respectively, the probability reliability of the partial order ‘\( \succ \)’, ‘\( \prec \)’ between a i and a j are:

$$ \begin{gathered} P\left( {a_{i} \succ a_{j} } \right) = \iint\limits_{x \ge y} {f_{i} (x)f_{j} (y)}dxdy, \hfill \\ P\left( {a_{i} \prec a_{j} } \right) = \iint\limits_{x \le y} {f_{i} (x)f_{j} (y)}dxdy. \hfill \\ \end{gathered} $$
(42.1)

Definition 5

For any two interval numbers a i , a j , if \( P\left( {a_{i} \succ a_{j} } \right) > 0.5 \), we set a i  \( \succ \) a j ; if \( P(a_{i} \succ a_{j} ) < 0.5 \)’ we set a i  \( \prec \) a j ; if \( P\left( {a_{i} \succ a_{j} } \right) = 0.5 \), we set a i  = a j .

The summation and maximum operations are used to solve the FJSSP, therefore, we define aggregate and maximization below:

Definition 6

For discrete interval numbers a i and a j , aggregate operation \( \oplus \) is given as follows:

$$ \tilde{a}_{i} \oplus \tilde{a}_{j} = \left[ {a_{i}^{ - } + a_{j}^{ - } ,a_{i}^{ + } + a_{j}^{ + } } \right]. $$
(42.2)

2.2 Problem Discussion

The n × m FJSSP can be described as follows: The scheduling system consists of a job set {J 1, J 2,…, J n } and a machine set {M 1, M 2,…, M m }. There are exist precedence constraints, therefore for each job J i is composed of several operations {O i1, O i2,…, O in }. In the meantime, owing to the constraints of executable, each operation O ij requires uninterrupted and exclusive special machine in its whole processing time. Additionally, deadline of each job has to be considered in the thesis. Other constraints in JSSP are also suitable for FJSSP. We summarize main notations being used in this thesis for your reference as follows:

n :

The amount of jobs in scheduling system;

m :

The amount of operations in scheduling system;

T = [t ij ]n × m:

The processing time matrix, where t ij denotes the processing time of O ij ;

W = [w ij ]n × m:

The execution machine matrix, where w ij denotes processing machine of O ij ;

W = {d1,d2,…,d n }:

The deadline vector, where d i denotes the deadline of job i ;

X = [x ij ]n × m:

The priority execution matrix, where x ij is an integer in [1, mn] to denote the priority execution ranking of O ij ;

TB = [tb ij ]n × m:

The beginning time matrix, where tb ij denotes the beginning time of O ij ;

TE = [te ij ]n × m:

The end time matrix, where te ij denotes the completion time of O ij ;

The solution of FJSSP is the process of matching job tasks and machine resources being connected with time and space. We have confronted with two issues, i.e., assigning each operation to an appropriate machine and also ranking the sequence for all operations. There are several strict constraints must be followed:

  1. (1)

    Each machine can only execute one job once at the same time, and the jobs assigned to the same machines should be executed in order;

  2. (2)

    Each job has a unique priority of execution, i.e., any two jobs have different execution order;

  3. (3)

    Only one operation of a job can be executed at one time and the times of executions should no more than one;

  4. (4)

    All operations of a job should be executed in order, and the completion time is determined by the last operation;

  5. (5)

    Each operation is assigned to the fixed machine in advance, and the working time is no less than the required time;

  6. (6)

    Preemptive is not allowed; therefore the operation will be retained until completion.

Deadline is one of the most important factors and the scheduling planning must take it in consideration, namely, the operations must be completed in their due time. Therefore, the degree of agreement has been set up as an optimization objective in our thesis.

Definition 7

Agreement index (AI) is the expected value of those jobs which have been completed prior to deadline. It is approximated as follows:

$$ \begin{gathered} AI = \sum\limits_{i = 1}^{n} {\mu (te_{im} ,d_{i} )} , \hfill \\ \mu (a_{i} ,a_{j} ) = \int\limits_{{a_{i}^{ - } }}^{{a_{i}^{ + } }} {f_{i} (x)F_{j} (x)} \,dx. \hfill \\ \end{gathered} $$
(42.3)

where f i (x) is the probability density function of a i ; F i (x) is the probability distribution function of a j .

Based on the constraints described previously, FJSSP can be converted into constraint satisfaction problem (CSP), and the CSP model is given as:

$$ \begin{gathered} {\text{Max}}\;z = AI \hfill \\ s.t.\left\{ \begin{gathered} te_{ij} \prec tb_{ij} ,\;if\;(x_{ij} < x_{kj} ) \wedge (w_{ij} = w_{kj} ), \hfill \\ x_{ij} \ne x_{kl} ,\;if\;(i \ne k) \vee (j \ne l), \hfill \\ (te_{ij} \prec tb_{il} ) \wedge (tb_{ij} \prec te_{il} ),\;if\;j < l, \hfill \\ x_{ij} < x_{il} ,\;if\;j < l, \hfill \\ te_{ij} \succ tb_{ij} \oplus t_{ij} , \hfill \\ (te_{ij} \prec tb_{il} )\; \vee \;(tb_{ij} \succ te_{il} ),\;if\;w_{ij} = w_{il} , \hfill \\ i,k \in [1,n],j,l \in [1,m]. \hfill \\ \end{gathered} \right. \hfill \\ \end{gathered} $$
(42.4)

where AI is the optimization objective of CSP model, and Eq. (42.4) corresponds with the mentioned six constraints.

3 Algorithm Designing

3.1 The Architecture of Algorithm

The IPSO algorithm has been employed to find the solution of the present combinatorial optimization problem. The efficiency of IPSO algorithm is reflected in its fast search ability. However, the convergent speed depends substantially on initial swarm and tends to integrate into local optimization. Consequently, we hereby combine PSO with genetic algorithm (GA) and heuristic algorithms, and then a novel improved PSO (IPSO) is generated as Algorithm 1.

3.2 Heuristic Algorithm

To improve the search efficiency of scheduling method, three heuristic algorithms are proposed and applied to produce the initialized elitism particles.

3.2.1 EDF Algorithm

The earliest deadline first (EDF) algorithm mainly picks up each job according to corresponding deadline in non-descending order. In particular, since deadline is a fuzzy variable, we sort the jobs with the partial order of due time and arrange the scheduling prior sequence based on the ranking result.

3.2.2 SPTF/LPTF Algorithm

The shortest/longest processing time first (SPTF/LPTF) algorithm priority is used to calculate the process time of each job and select the job which consumes the minimum/maximum process time for executing object.

3.2.3 LNDF Algorithm

The largest nearby degree first (LNDF) algorithm will select the job which has the nearest processing time to its deadline. The degree of closeness for job i can be defined as:

$$ Var_{i} = \mu \left( {\sum\limits_{j = 1}^{m} {t_{ij} } ,d_{i} } \right) $$
(42.5)

3.3 Algorithm Representation

In the thesis, we encode particles with job numbers, and the chromosome denotes the executing priority sequence of operations. For an n × m FJSSP, the n × m length chromosome is established. Each gene represents a special operation, which is expressed in a gene no more than m. The moving vector is designed to implement moving operation, and a chromosome is realized by ranking its moving vector in non-descending order. The chromosome is transferred into a decision matrix in encoding process, and then we can calculate the beginning time and completion time of each operation according to the processing route. The decoding method of particle is designed as Algorithm 2.

4 Computation Experiments

In this section, a simulation program is manipulated in Matlab2007 on a personal computer with Pentium IV 3.06GHZ CPU. To test the efficiency of IPSO, we compare it with GA and PSO in twelve benchmark problems (e.g. LA01, LA07, LA11, LA19, LA21, LA27, SWV06, SWV08, SWV10, YN1, YN2 and YN3) and the GA and PSO also adopt the same parameters in IPSO. Given the variables in twelve benchmark problems are certain values, we use triangle interval numbers and trapezoid interval numbers to realize the fuzzy disposition of processing time and deadline respectively.

From Table 42.1, we can find out obviously that the IPSO algorithm has eight solutions better than GA. There are four equations, and only one of them is worse than GA. At the same time, only three solutions of IPSO have the same values as PSO, but the CPU time is 5.25 % longer than PSO since the mutation operation are involved in the IPSO. This experiment shows that IPSO can avert early convergence and also search for more optimal solutions, which means high efficiency could be achieved.

Table 42.1 Summary results of the different algorithms
Full size table

5 Conclusion

In the thesis, FJSSP with fuzzy processing time and fuzzy deadline has been analyzed. We covert the FJSSP to CSP by defining fuzzy priority rules, in addition, IPSO algorithm is proposed to solve the problem. Heuristic algorithms are combined with the PSO algorithms to improve the search ability of the latter issue. The experiment results have proved the effectiveness of the methods being employed.