Swarm lexicographic goal programming for fuzzy open shop scheduling

Abstract

In this work we consider a multiobjective open shop scheduling problem with uncertain processing times and flexible due dates, both modelled using fuzzy sets. We adopt a goal programming model based on lexicographic multiobjective optimisation of both makespan and due-date satisfaction and propose a particle swarm algorithm to solve the resulting problem. We present experimental results which show that this multiobjective approach achieves as good results as single-objective algorithms for the objective with the highest priority, while greatly improving on the second objective.

Introduction

The open shop scheduling problem (OSP) is a problem with an increasing presence in the literature and clear applications in industry—consider for instance testing facilities where units go through a series of diagnostic tests that need not be performed in a specified order and where different testing equipment is usually required for each test (see Pinedo 2008). For a number of machines $m\ge 3$ this problem is NP-complete; in consequence, it is usually tackled via metaheuristics techniques. For instance, for makespan minimisation, Guéret and Prins (1998) describe two heuristic methods to obtain a list of operation priorities later used in a list-scheduling algorithm; Liaw (1999) proposes a tabu search algorithm; Blum (2005) hybridises ant colony optimisation with beam search and Sha and Cheng-Yu (2008) propose a solution based on particle swarm optimisation. To minimise total tardiness, Naderi et al. (2011) propose two metaheuristics based on genetic algorithms and variable neighbourhood search and for multiobjective open shop we find an ant colony algorithm combined with simulated annealing in Panahi et al. (2008) and particle swarm optimisation in Sha et al. (2010).

Traditionally, scheduling has been treated as a deterministic problem that assumes precise knowledge of all data involved, in contrast with the uncertainty and vagueness pervading real-world problems. To enhance the range of applications of scheduling, an increasing part of the research is devoted to modelling this lack of certainty with great diversity of approaches (Herroelen and Leus 2005). In particular, fuzzy sets have been used in different manners, ranging from representing incomplete or vague states of information to using fuzzy priority rules with linguistic qualifiers or preference modelling and as an interesting tool for improving solution robustness and stability (Guiffrida and Nagi 1998; Dubois et al. 2003; Petrovic et al. 2008).

Far from being trivial, extending heuristic strategies to uncertain settings usually requires a significant reformulation of both the problem and solving methods. This is patent in the available literature on job shop problems with uncertain processing times and/or flexible constraints. For instance, Dubois et al. (1995) extend a constrained-based approach, Fortemps (1997) uses simulated annealing and Sakawa and Kubota (2000) propose a genetic algorithm in what can be seen as pioneering works in the application of metaheuristic strategies, followed by many authors, e.g. González Rodríguez et al. (2008), Puente et al. (2010), Niu et al. (2008) or Zheng et al. (2011). However, while there are many contributions to solve fuzzy job shop problems, the literature on fuzzy open shop is still scarce. Indeed, the open shop with uncertainty constitutes a relatively new and complex research line. Among the few existing proposals, in (Alcaide et al. 2006) a heuristic approach is proposed to minimise the expected makespan for an open shop problem with stochastic processing times and random breakdowns; González-Rodríguez et al. (2010) minimise the expected makespan of an open shop with fuzzy durations using a genetic algorithm hybridised with local search, while Palacios et al. (2011) use a particle swarm optimisation algorithm for the same problem. Finally, a possibilistic mixed-integer linear programming method is proposed in Noori-Darvish et al. (2012) for an OSP with setup times, fuzzy processing times and fuzzy due dates to minimise total weighted tardiness and total weighted completion times.

Another issue that must be taken into account to reduce the gap between academic and real-world problems is the fact that many real-life applications require taking into account several conflicting points of view corresponding to multiple objectives. This is one of the reasons why the applications of multiobjective decision making techniques in engineering have grown in the recent decades (Pasandideh and Niaki 2013). Although Pareto optimality is undoubtedly the most extended approach to multicriteria optimisation, as Ehrgott (2005) puts it, “it is not the end of the story”, with other approaches to multiobjective optimisation in the literature (Ehrgott and Gandibleux 2000). Among these techniques, lexicographic and goal programming methods are some of the most popular ones (Farahani et al. 2010). The philosophy behind goal programming (Romero 2001) can be traced back to the theories of rational decision developed in the 1950s, especially the concept of satisficing solutions: in a complex environment, the decision maker’s aim may be to reach a certain satisfactory level for every relevant objective, rather than optimising its value. Also, lexicographic problems arise naturally when conflicting objectives exist in a decision problem but for reasons outside the control of the decision maker the objectives have to be considered in hierarchical manner. Recent examples of real-world problems where these techniques are applied can be found, for instance, in Ehrgott (2005), Diaz-Balteiro and Romero (2008), Puente et al. (2013), Coshall and Charlesworth (2011), and Liberatore et al. (2013). Additionally, there exist interesting relationships between lexicographic and Pareto-optimal solutions. Indeed, “lexicographic minimisation is well-suited to seek a compromise between conflicting interests, as well as reconciling this requirement with the crucial notion of Pareto-optimality” (Bouveret and Lemaître 2009).

To our knowledge, a lexicographical goal programming approach to solve multiobjective instances of fuzzy open shop has never been taken in the still scarce literature on this problem. This paper attempts to contribute to filling this gap. To this end, in the sequel we propose a multiobjective particle swarm optimisation (MOPSO) algorithm to solve instances of open shop where uncertain processing times are modelled with triangular fuzzy numbers and flexible due dates are modelled with fuzzy sets. In “Uncertain processing times and flexible constraints” section we provide some background on fuzzy sets, which will be used in “The fuzzy open shop scheduling problem” section to formulate the Fuzzy Open Shop Problem (FOSP). We adopt a lexicographic goal programming approach to define an objective function which combines minimisation of the expected fuzzy makespan and maximisation of overall due-date satisfaction. The resulting problem is solved by means of a particle swarm optimization method searching in the space of possibly active schedules, as proposed in “Particle swarm optimization for the FOSP” section. “Experimental results” section reports results from the experimental study which illustrate the potential of the proposed method. Finally, in “ Conclusions and future work” section we summarise the main conclusions and propose some ideas for future work.

Uncertain 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. However, based on previous experience, an expert may be able to estimate, for instance, an interval for the possible processing time or its most typical value. In literature, it is common to use fuzzy intervals to represent such processing times, as an alternative to probability distributions, which require a deeper knowledge of the problem and usually yield a complex calculus.

Fuzzy interval arithmetic to model processing times

Fuzzy intervals are a natural extension of human originated confidence intervals when some values appear to be more plausible than others. The simplest model is a triangular fuzzy number or TFN, using an interval $[a^1,a^3]$ of possible values and a single plausible value $a^2$ in it. For a TFN $A$, denoted $A=(a^1, a^2, a^3)$, the membership function takes the following triangular shape:

$$\begin{aligned} \mu _A(x)={\left\{ \begin{array}{ll} \frac{x-a^1}{a^2-a^1} &{}: a^1 \le x \le a^2\\ \frac{x-a^3}{a^2-a^3} &{}: a^2 < x \le a^3\\ 0 &{} : x<a^1 \text { or } a^3 < x\\ \end{array}\right. } \end{aligned}$$

(1)

Triangular fuzzy numbers and more generally fuzzy intervals have been extensively studied in the literature (cf. Dubois and Prade 1986). A fuzzy interval $Q$ is a fuzzy quantity (a fuzzy set on the reals) whose $\alpha$-cuts $Q_\alpha =\{u \in \mathbb {R}: \mu _Q(u) \ge \alpha \}$, $\alpha \in (0.1]$, are convex, i.e. they are intervals (bounded or not). The core of $Q$ consists of those elements with full membership $\mu _Q(u)=1$, also called modal values and its support is $Q_0=\{u \in \mathbb {R}: \mu _Q(u)>0\}$. A fuzzy number is a fuzzy quantity whose $\alpha$-cuts are closed intervals, with compact (i.e. closed and bounded) support and unique modal value. Thus, real numbers can be seen as a particular case of fuzzy ones.

In order to work with fuzzy numbers, it is necessary to extend the usual arithmetic operations on real numbers. In general, if $f$ is a function $f:\mathbb {R}^2 \rightarrow \mathbb {R}$ and $Q_1$, $Q_2$ are two fuzzy quantities, the fuzzy quantity $f(Q_1,Q_2)$ is calculated according to the Extension Principle. However, computing the resulting equation is in general cumbersome, if not intractable. It can be somewhat simplified for two fuzzy numbers $M$ and $N$, so the $\alpha$-cuts $M_\alpha$ and $N_\alpha$ are closed bounded intervals of the form $[\underline{m}_\alpha , \overline{m}_\alpha ]$ and $[\underline{n}_\alpha ,\overline{n}_\alpha ]$, if $f$ is a continuous isotonic mapping from $\mathbb {R}^2$ into ${\mathbb {R}}$, that is, if for any $u\ge u'$ and $v \ge v'$ it holds $f(u,v)\ge f(u',v')$. In this case, the First Decomposition Theorem provides us with an alternative formula for $f(M,N)$:

$$\begin{aligned} f(M,N)=\cup _{\alpha \in (0,1]}[f(\underline{m}_\alpha ,\underline{n}_\alpha ), f(\overline{m}_\alpha ,\overline{n}_\alpha )] \end{aligned}$$

(2)

In the open shop, we essentially need the following operations on fuzzy durations: addition and maximum. In the case of TFNs, the addition is fairly easy to compute, since it is reduced to operating on the three defining points, that is, for any pair of TFNs $M$ and $N$:

$$\begin{aligned} M+N=(m^1+n^1, m^2+n^2, m^3+n^3). \end{aligned}$$

(3)

Unfortunately, for the maximum of TFNs there is no such simplified expression. Being an isotonic function, we can use Eq. (2) above, but in general this still requires an infinite number of computations, since we have to evaluate maxima for each value $\alpha \in (0,1]$. For the sake of simplicity and tractability of numerical calculations, we follow (Fortemps 1997) and approximate all results of isotonic algebraic operations on TFNs by a TFN. Instead of evaluating the intervals corresponding to all $\alpha$-cuts, we evaluate only those intervals corresponding to the support and $\alpha =1$, which is equivalent to working only with the three defining points of each TFN. This is an approach also taken, for instance, in Niu et al. (2008) and Chen and Chang (2001). Therefore, for any two TFNs $M$ and $N$, their maximum will be approximated as follows:

$$\begin{aligned}&\max (M,N)\sim M \sqcup N = (\max (m^1, n^1),\nonumber \\&\quad \max (m^2, n^2), \max (m^3,n^3)). \end{aligned}$$

(4)

Despite not being equal, for any two TFNs $M,N$, if $F=\max (N,M)$ denotes their maximum and $G=N \sqcup M$ its approximated value, it holds that $\forall \alpha \in [0,1],\quad \underline{f}_\alpha \le \underline{g}_\alpha , \overline{f}_\alpha \le \overline{g}_\alpha$. In particular, $F$ and $G$ have identical support and modal value: $F_0=G_0$ and $F_1=G_1$. The approximated maximum can be trivially extended to $n>2$ TFNs.

For a fuzzy number $N$, its membership function $\mu _N$ can be interpreted as a possibility distribution on the real numbers. This allows to define the expected value of a fuzzy number (Liu and Liu 2002), given for a TFN $A$ by

$$\begin{aligned} E[A]=\frac{1}{4}(a^1+2a^2+a^3). \end{aligned}$$

(5)

The expected value coincides with the neutral scalar substitute of a fuzzy interval and can also be obtained as the centre of gravity of its mean value or using the area compensation method (Dubois et al. 2003). It induces a total ordering $\le _E$ in the set of fuzzy intervals (Fortemps 1997), where for any two fuzzy intervals $M, N$ $M \le _E N$ if and only if $E[M] \le E[N]$.

Modelling flexible due dates

In practice, if due-date constraints exist, they are often flexible. For instance, customers may have a preferred delivery date $d^1$, but some delay will be allowed until a later date $d^2$, after which the order will be cancelled. The satisfaction of a due-date constraint becomes a matter of degree, our degree of satisfaction that a job is finished on a certain date. A common approach to modelling such satisfaction levels is to use a fuzzy set $D$ with linear decreasing membership function:

$$\begin{aligned} \mu _D(x)={\left\{ \begin{array}{ll} 1 &{} : x \le d^1\\ \frac{x-d^2}{d^1-d^2} &{} : d^1 < x \le d^2\\ 0 &{} : d^2 < x\\ \end{array}\right. } \end{aligned}$$

(6)

This expresses a flexible threshold “less than”, representing the satisfaction level $sat(t)=\mu _D(t)$ for the ending date $t$ of the job (Dubois et al. 2003). When the job’s completion time is no longer a real number $t$ but a TFN $C$, the degree to which $C$ satisfies the due-date constraint $D$ may be measured using the following agreement index (Sakawa and Kubota 2000; Celano et al. 2003):

$$\begin{aligned} AI(C,D) = \frac{area (D \cap C)}{area (C)} \end{aligned}$$

(7)

where $area(D \cap C)$ and $area (C)$ denote the areas under the membership functions of $(D \cap C)$ and $C$ respectively. The intuition behind this definition is to measure the degree to which $C$ is contained in $D$ (the degree of subsethood).

The fuzzy open shop scheduling problem

The open shop scheduling problem, or OSP in short, consists in scheduling a set of $n$ jobs $J_1,\dots ,J_n$ to be processed on a set of $m$ physical resources or machines $M_1,\dots ,M_m$. Each job $J_i$ consists of $m$ tasks or operations $o_{ij}$ $(j=1,\dots ,m)$, where $o_{ij}$ requires the exclusive use of a machine $M_j$ for its whole processing time $p_{ij}$ without preemption, i.e. all tasks must be processed without interruption. In total, there are $mn$ tasks. Additionally, for each job $J_i$ there may be a due date $d_i$, $i=1,\dots ,n$ before which it is desirable that the job be finished. A solution to this problem is a schedule (a starting time for all tasks) which, besides being feasible, in the sense that precedence and capacity constraints hold, is optimal according to some criteria, for instance, that due-date satisfaction is maximal or that the project’s makespan is minimal.

Fuzzy schedules from crisp task orderings

A schedule $s$ for an open shop problem of size $n \times m$ ($n$ jobs and $m$ machines) may be determined by a decision variable $\mathbf z =(z_1,\ldots ,z_{nm})$ representing a task processing order, where $1 \le z_l \le nm$ for $l=1,\ldots ,nm$. This is a permutation of the set of tasks where each task $o_{ij}$ is represented by the number $(i-1)m+j$. The task processing order represented by the decision variable uniquely determines a feasible schedule; it should be understood as expressing partial orderings for every set of tasks requiring the same machine and for every set of tasks belonging to the same job.

Let us assume that the processing time $p_{ij}$ of each task $o_{ij}$, $i=1,\ldots ,n$, $j=1,\ldots ,m$ is a fuzzy variable (a particular case of which are TFNs), so the problem may be represented by a matrix of fuzzy processing times $\mathbf p$ of size $n \times m$. For a given task processing order $\mathbf z$ and a task $o_{ij}$, its starting time $S_{ij}(\mathbf z ,\mathbf p )$ is the maximum (Eq. 4) between the completion times of the task preceding $o_{ij}$ in its job, let it be denoted $o_{ik}$, and the task preceding $o_{ij}$ in its machine, let it be denoted $o_{lj}$:

$$\begin{aligned} S_{ij}(\mathbf z ,\mathbf p ) = C_{ik}(\mathbf z ,\mathbf p ) \sqcup C_{lj}(\mathbf z ,\mathbf p ) \end{aligned}$$

(8)

where $C_{ik}(\mathbf z ,\mathbf p )$ or $C_{lj}(\mathbf z ,\mathbf p )$ are taken to be zero if $o_{ij}$ is the first task to be processed either in its job or its machine. Then, its completion time $C_{ij}(\mathbf z ,\mathbf p )$ is obtained by adding its duration $p_{ij}$ to $S_{ij}(\mathbf z ,\mathbf p )$:

$$\begin{aligned} C_{ij}(\mathbf z ,\mathbf p ) = S_{ij}(\mathbf z ,\mathbf p ) + p_{ij} \end{aligned}$$

(9)

The completion time of a job $J_i$ will then be the maximum completion time of all its tasks, that is, $C_i(\mathbf z ,\mathbf p )=\sqcup _{1\le j \le m} \{C_{ij}(\mathbf z ,\mathbf p )\}$.

For this schedule, the fuzzy makespan $C_{max}(\mathbf z , \mathbf p )$ is defined as the maximum of job completion times:

$$\begin{aligned} C_{max}(\mathbf z , \mathbf p ) = \sqcup _{1 \le i \le n}\left( C_i(\mathbf z ,\mathbf p ) \right) \end{aligned}$$

(10)

Notice that when uncertain durations are given as fuzzy intervals the schedule $s$ will be fuzzy in the sense that the starting and completion times of all tasks as well as the makespan are fuzzy intervals. These may be interpreted as possibility distributions on the values that each time may take. Fuzzy intervals are thus used to represent our incomplete knowledge of problem parameters related to durations and, in consequence, our incomplete knowledge of starting and completion times for all tasks. However, the task processing order represented by $\mathbf z$ that determines such schedule is crisp: there is no uncertainty regarding the order in which tasks are to be processed.

Given a fuzzy schedule, it is necessary to give a precise definition of what “optimal makespan” means, since neither the maximum nor its approximation define a total ordering in the set of TFNs. Using ideas similar to stochastic scheduling, we use the total ordering provided by the expected value and consider that the objective of minimising the makespan translates, in practice, into minimising its expected value $E[C_{max}]$ (Eq. 5).

While also being fuzzy sets, due dates $d_i$ for jobs $J_i$, $i=1,\ldots ,n$, do not model uncertainty. Instead, they model flexible constraints, introducing grades in the traditionally Boolean notion of feasibility (cf. Dubois 2011) and the references therein for the semantics of fuzzy sets and their role in decision making). In this setting, the agreement index, $AI(C_i(\mathbf z ,\mathbf p ),d_i)$ (Eq. 7), denoted $AI_i(\mathbf z ,\mathbf p )$ for short, measures to what degree the flexible due date $d_i$ is satisfied by the fuzzy time $C_i(\mathbf z ,\mathbf p )$. The degree of overall due-date satisfaction for schedule $s$ may then be obtained by aggregating the satisfaction degrees $AI_i(\mathbf z ,\mathbf p )$, $i=1,\ldots ,n$. In particular, we shall consider two aggregation functions, the minimum and the average, previously used in the literature concerning shop scheduling with soft constraints, for instance, in Sakawa and Kubota (2000), González Rodríguez et al. (2008), Lei (2008). The minimum is inspired by the seminal paper on fuzzy decision making (Bellman and Zadeh 1970), while the average provides an alternative for which the compensation property holds. Hence, the degree $AI_{ag}(\mathbf z ,\mathbf p )$ to which a schedule $s$ determined by an ordering $\mathbf z$ satisfies due dates will be determined by one of the two following formula:

$$\begin{aligned}&AI_{av}(\mathbf z ,\mathbf p ) = \frac{1}{n} \sum _{i=1}^{n} AI_i(\mathbf z ,\mathbf p ),\end{aligned}$$

(11)

$$\begin{aligned}&AI_{min}(\mathbf z ,\mathbf p ) = \min _{i=1,\dots ,n} AI_i(\mathbf z ,\mathbf p ) \end{aligned}$$

(12)

Clearly both $AI_{av}(\mathbf z ,\mathbf p )$ and $AI_{min}(\mathbf z ,\mathbf p )$ should be maximised. Notice however that they model different requirements and encourage different behaviours. In the cases when there is no possible confusion regarding the order $\mathbf z$ or the processing times $\mathbf p$, we may simplify the notation and write $AI_{ag}$ or $C_{max}$.

Let us illustrate the previous definitions with an example. Consider a problem of 3 jobs and 2 machines with the following matrices for fuzzy processing times and due dates:

$$\begin{aligned} \mathbf p =\begin{pmatrix} ( 3, 4, 7) &{} ( 3, 4, 7)\\ ( 2, 3, 4) &{} ( 4, 5, 6)\\ ( 3, 4, 5) &{} ( 1, 2, 6) \end{pmatrix} \mathbf d =\begin{pmatrix} ( 11, 21)\\ ( 6, 10)\\ ( 12, 15) \end{pmatrix} \end{aligned}$$

Here $p_{21}=(2,3,4)$ is the processing time of task $o_{21}$, the task of job $J_2$ to be processed in machine $M_1$ and $d_2=(6,10)$ is the flexible due date for job $J_2$. Figure 1a, b show the Gantt charts (both machine and job oriented) adapted to TFNs of the schedule given by the decision variable $\mathbf z =(1, 4, 6, 3, 5, 2)$. They represent the partial schedules on each machine and each job obtained from this decision variable. Tasks must be processed in the following order: $o_{11}, o_{22}, o_{32}, o_{21}, o_{31}, o_{12}$. Given this ordering, the starting time for task $o_{21}$ will be the maximum of the completion times of $o_{22}$ and $o_{11}$, which are respectively the preceding tasks in the job and in the machine: $S_{21}=C_{22} \sqcup C_{11}=(4,5,6)\sqcup (3,4,7)=(4,5,7)$. Consequently, its completion time will be $C_{21}=S_{21}+ p_{21}=(4,5,7)+(2,3,4)=(6,8,11)$. Also, it is easy to see that $C_{max}=(9,12,19)$ (see Fig. 1a), so $E[C_{max}]=13$. Regarding due dates, in Fig. 1b we can see that the completion time of job $J_1$ always satisfies its due date, so $AI_1 =1$, whereas for job $J_2$ $area (C_2)= 5/2$ and $area (d_2 \cap C_2)=4/3$, so $AI_2 = 0.53$, and analogously $AI_3 = 0.75$. Hence, the aggregated degrees of due date satisfaction will be $AI_{min}=0.53$ and $AI_{av}=0.76$.

Fig. 1

Gantt charts of the schedule represented by the decision variable (1, 4, 6, 3, 5, 2). a Machine oriented, b Job oriented

Multiobjective model

For the fuzzy open shop problem we are interested both in maximising the aggregated due-date satisfaction $AI_{ag}$ and minimising the expected makespan $E[C_{max}]$. A well-established approach dealing with multiple and possibly conflicting objectives is lexicographic goal programming (Ehrgott 2005; Tamiz et al. 1998), assuming that the decision makers establish a priority structure as well as target levels for the different objectives.

Before we formulate the resulting problem, notice that $AI_{ag}(\mathbf z ,\mathbf p )\in [0,1]$ for both aggregation operators. Hence, maximising $AI_{ag}(\mathbf z ,\mathbf p )$ is equivalent to minimising $1-AI_{ag}(\mathbf z ,\mathbf p )$, which could be interpreted as the degree to which due dates are violated. In consequence, we can restate the objective of our problem as minimising both $E[C_{max}(\mathbf z ,\mathbf p )]$ and $1-AI_{ag}(\mathbf z ,\mathbf p )$.

Let $C_{max}$ and $1-AI_{ag}$ be ordered according to their priority, and let $f_1$ denote the objective with highest priority and $f_2$ denote the secondary objective. Also, let us assume that the decision makers establish target values $b_1, b_2 \ge 0$ for $f_1$ and $f_2$. Clearly, these values should not be exceeded, which translates into the following goal constraints:

$$\begin{aligned} f_i(\mathbf z ,\mathbf p ) + \varDelta _i^- - \varDelta _i^+ = b_i, \quad i=1,2 \end{aligned}$$

(13)

where $\varDelta _1^+, \varDelta _2^+ \ge 0$, the positive deviations from the targets, should be minimised. This results in the following lexicographic goal programming model for the fuzzy open shop problem (FOSP):

$$\begin{aligned} {\left\{ \begin{array}{ll} {{\mathrm{lexmin}}}&{} (\varDelta _1^+, \varDelta _2^+)\\ \text {subject to:} &{} \\ &{} f_i(\mathbf z ,\mathbf p ) +\varDelta _i^- - \varDelta _i^+ = b_i, \quad i=1,2,\\ &{} b_i \ge 0, \quad i=1,2,\\ &{} \varDelta _i^-, \varDelta _i^+ \ge 0,\\ &{} 1 \le z_l \le nm, \quad l=1,\dots ,nm,\\ &{} z_l \ne z_k, \quad k \ne l\\ &{} z_l \in \mathbb {Z}^+, \quad l=1,\dots ,nm,\\ \end{array}\right. } \end{aligned}$$

(14)

where ${{\mathrm{lexmin}}}$ denotes lexicographically minimising the objective vector $(\varDelta _1^+,\varDelta _2^+)$.

The resulting problem can be denoted $O|fuzz\;p_i, fuzz\;d_i|LexGP(E[C_{max}],1-AI_{av})$ according to the three-field notation from (Graham et al. 1979), extended to multicriteria scheduling in the spirit of T’kindt and Billaut (2006).

Particle swarm optimization for the FOSP

Particle swarm optimisation (PSO) is a population-based stochastic method inspired by bird flocking or fish schooling, first proposed in Kennedy and Eberhart (1995) which has been successfully applied to solve complex combinatorial optimization problems; recent examples of this success can be found in Belmecheri et al. (2013), Jia and Seo (2013), and Kim and Son (2012). In particular, it has been applied to scheduling problems, among others, in Tassopoulos and Beligiannis (2012), Vijay Chakaravarthy et al. (2013), and Marinakis and Marinaki (2013) as well as the already mentioned references devoted to the open shop problem (Sha and Cheng-Yu 2008; Sha et al. 2010).

In PSO, each position in a multidimensional search space corresponds to a solution of the problem and particles in the swarm cooperate to explore the space and find the best position (hence best solution). Particle movement is mainly affected by the three following factors:

• Inertia: Velocity of the particle in the latest iteration,

• pbest: The best position found by the particle,

• gbest: The best position found by the swarm so far (“the best $pbest$”),

Potential solutions are represented by multidimensional particles flying through the problem space, changing their position and velocity by following the current optimum particles $pbest$ and $gbest$. A generic PSO algorithm is given in Algorithm 1: first, the initial swarm is generated and evaluated and then the swarm evolves until a termination criterion is satisfied. In each iteration, a new swarm is built from the previous one by changing the position and velocity of each particle to move towards its $pbest$ and $gbest$ locations.

In the following, we present a multiobjective PSO algorithm for the FOSP with lexicographic goal programming defined in the previous section. A preliminary version of this algorithm was presented in Palacios et al. (2011) to minimise the expected makespan of fuzzy open shop.

Position representation and evaluation

For each particle $k$ in the swarm, its position $\mathbf x ^k$ is represented with a priority-based representation. Thus, the decision variable $\mathbf z ^k$ is encoded as a priority array $\mathbf x ^k = (x^k_{l})_{l=1\ldots nm}$ where $x^k_{l}$ denotes the priority of task $l$, so a task with smaller $x^k_{l}$ has a higher priority to be scheduled.

Given a FOSP solution represented by a decision variable $\mathbf z$, which is a permutation of tasks, we can transfer this permutation to a priority array as follows. First, from $\mathbf z$ we obtain a position array, denoted $pos^\mathbf{z }$, such that $pos^\mathbf{z }_l$ is the position of task $l$ in $\mathbf z$ ($pos^\mathbf{z }_l=i$ if and only if $z_i=l$). For instance, for a problem with $n=2$ jobs and $m=3$ machines we can have a decision variable $\mathbf z$ and the corresponding position array $pos^\mathbf{z }$ as follows:

$$\begin{aligned} \mathbf z = (4, 1, 5, 2, 3, 6) \qquad \mathbf pos ^\mathbf{z } = (2, 4, 5, 1, 3, 6) \end{aligned}$$

Then, the priority array $\mathbf x$ is obtained by randomly setting $x_l$ in the interval $\left( pos^\mathbf{z }_l-0.5, pos^\mathbf{z }_l+0.5\right)$, so a task with smaller $x_l$ has higher priority to be scheduled. For the above decision variable, a possible particle position would be:

$$\begin{aligned} \mathbf x = (2.3, 3.7, 5.4, 0.8, 2.8, 5.9) \end{aligned}$$

Conversely, from every particle position $\mathbf x$ we can obtain a position array $\mathbf {pos} ^\mathbf{x }$ (and the corresponding decision variable) where $pos^x_i$ is the position of $x_i$ if the elements of $\mathbf x$ were reordered in non-decreasing order.

A particle may be decoded in several ways. For deterministic job shop and, by extension, for open shop scheduling, it is common to use the G&T algorithm (Giffler and Thompson 1960), which is an active schedule builder. A schedule is active if one task must be delayed for any other one to start earlier. Active schedules are good in average and, most importantly, the space of active schedules contains at least an optimal one, that is, the set of active schedules is dominant. For these reasons it is worth to restrict the search to this space. In Gonçalves et al. (2005) a narrowing mechanism was incorporated to the G&T algorithm in order to limit machine idle times using a delay parameter $\delta \in [0,1]$, thus searching in the space of so-called parametrised active schedules. In the deterministic case, for $\delta < 1$ the search space is reduced so it may no longer contain optimal schedules and at the extreme $\delta =0$ the search is constrained to non-delay schedules where a resource is never idle if a requiring operation is available. This variant of G&T has been applied in Sha and Cheng-Yu (2008) to the deterministic OSP, under the name “parameterized active schedule generation algorithm”. Algorithm 2, denoted $pFG \& T$, is an extension of parametrised G&T to the case of fuzzy processing times proposed in Palacios et al. (2011). Throughout the algorithm, $\varOmega$ denotes the set of tasks that have not been scheduled yet, $\mathbf x ^k$ denotes the priority array and $S_l$ and $C_l$ denote the starting and completion time of task $o_{ij}$ such that $l=(i-1)m+j$. It should be noted that, due to the uncertainty in task durations, even for $\delta =1$ we cannot guarantee that the produced schedule will indeed be active when it is actually performed (and tasks have exact durations). We may only say that the obtained fuzzy schedule is possibly active.

Particle movement

Velocity update

Particle velocity is traditionally updated depending on the distance to $gbest$ and $pbest$. Instead, this PSO only considers whether the position value $x_l^k$ is greater or smaller than $pbest_l^k$ ($gbest_l$). For any particle, its velocity is represented by an array of the same length as the position array where all the values are in the set $\{-1,0,1\}$. The initial values for the velocity array are set randomly. Velocity and particle updating is controlled by the inertia weight $w$ according to Algorithm 3. In the updating process of each particle $k$ and dimension $d$ an element of randomness is introduced, making it dependent on $pbest_d^k$ with probability $p_1$ and on $gbest_d$ with probability $p_2$, where $p_1,p_2 \in [0,1]$ are constants such that $p_1+p_2 \le 1$.

Mutation

When adapting PSO to discrete optimisation, there is a risk of getting stuck in local minima when velocity is limited to absolute values (Hu et al. 2003). In order to introduce diversity, after a particle $k$ moves to a new position, we randomly choose a dimension $d$ and then mutate its priority value $x_d^k$ independently of $v_d^k$. For a problem of size $n \times m$, if $x_d^k<\left( nm/2\right)$, $x_d^k$ will take a random value in $[mn-n,mn]$, and $v_d^k=1$; otherwise (if $x_d^k\ge \left( nm/2\right)$), $x_d^k$ will take a random value in $[0,n]$ and $v_d^k=-1$.

Diversification strategy

In the case that all particles had the same $pbest$ solution, they could be trapped into local optima. To prevent such situation, a diversification strategy is proposed in Sha and Cheng-Yu (2008) in order to keep the different $pbest$ solutions. According to this strategy, the $pbest$ solution of each particle is not the best solution found by the particle itself, but one of the best $N$ solutions found by the swarm so far, where $N$ is the size of the swarm. Once any particle generates a new solution, the $pbest$ solutions will be updated as follows: if the new solution equals the makespan of any $pbest$ solution, the latter will be replaced with the new solution; else if the new solution has better makespan than the worst $pbest$ solution and has a different makespan from all $pbest$ solutions, then the worst $pbest$ solution is replaced by the new one; else, the set of $N$ $pbest$ solutions remains unchanged.

Experimental results

For the experimental study, we use the fuzzy open shop instances proposed in González-Rodríguez et al. (2010). These were obtained by fuzzyfying the well-known benchmark from (Brucker et al. 1997), consisting of 6 families, denoted J3, J4, ..., J8, of sizes $3 \times 3$ to $8 \times 8$, with 8 or 9 instances each. Each family is divided into three sets of problems per0, per10 and per20 according to the difference between minimum and maximum workloads of jobs and machines (the number in the name refers to this difference in percentage). We shall only consider the largest instances, pertaining to the blocks of size $7 \times 7$ and $8 \times 8$ and compare our results on expected makespan to those of the memetic algorithm (MA) proposed in González-Rodríguez et al. (2010), which combines a genetic algorithm with a local search schema. According to the results reported in González-Rodríguez et al. (2010), this MA outperforms the genetic algorithm alone when run under equivalent running conditions; additionally, on crisp instances of OSP it improves two GAs from Liaw (2000) and Prins (2000) and is competitive with two PSO algorithms from Sha and Cheng-Yu (2008), one of them hybridised with beam search.

For each original deterministic problem instance there are 10 fuzzy versions, generated by transforming the original crisp processing times into symmetric TFNs such that their modal value corresponds to the original duration. To add a due date $d_i$ for each job $J_i$ we follow Andresen et al. (2008): first, we define a generic due date $d_i=T\!F \times \sum _{j=1}^m p_{ij}^2$, where $T\!F$ is a tightness factor; then, we use two different tightness factors to have the earliest and latest due dates: $d_i^1$, with $T\!F=1.10$, and $d_i^2$, with $T\!F=1.15$.

Given the method for generating due dates, in per0 instances, where all jobs have the same workload (and consequently the same due date), the makespan and due date satisfaction are strongly correlated objectives, making these instances unsuitable for our multiobjective study. Therefore, the experimental analysis will be conducted on the instances per10 and per20 of size $7 \times 7$ and $8 \times 8$, making it a total of 120 instances, these being the hardest ones to solve when both objectives are considered.

For each problem instance, we have run the PSO algorithm using different objectives: we have considered the three single-objective functions $E[C_{max}],AI_{av}$ and $AI_{min}$ and the four multiobjective functions that result from combining the two choices of aggregation function for due date satisfaction ($AI_{ag}=AI_{min}$ or $AI_{ag}=AI_{av}$) and the two possible priority structures for objectives ($f_1=C_{max},f_2=AI_{ag}$ or $f_1=AI_{ag}, f_2=C_{max}$).

For the multiobjective cases, it is necessary that the target values for both objectives be fixed. As already mentioned, in practice these target values should be given by the DM based on his/her expertise in the problem. Unfortunately, such expert knowledge is not available for the set of synthetic instances used herein. Instead, we emulate the DM and try to gain insight into the problem instances with some preliminary runs of the PSO using $E[C_{max}], AI_{av}$ and $AI_{min}$ as single objectives, using the parameter values proposed in Sha and Cheng-Yu (2008). Then, we set $b_1$ (resp. $b_2$ for $1-AI_{ag}$) equal to the worst value of $E[C_{max}]$ ($1-AI_{ag}$) across 30 runs of the PSO.

Parameter setting

To ensure that the algorithm yields reliable solutions within a reasonable amount of time, the Taguchi method is used for parameter tuning. Table 1 shows the parameters of our algorithm together with the four possible values (factor levels in the Taguchi terminology) considered for each of them. A caveat in changing the swarm size $N$ is its considerable effect on the algorithm’s runtime if a constant number of iterations is considered. Now, it is common in literature to measure the computational effort of a metaheuristic in terms of the number of objective-function evaluations, which is independent of the computer system. This suggests adjusting the number of iterations in such a way that the PSO evaluates roughly the same number of particles for all possible swarm sizes: for $N=60, 80, 100$ and 120, the number of iterations $Niter$ is set respectively to 3,000, 2,250, 1,800 and 1,500. As for the second parameter, the inertia weight $w$, it should be linearly decreasing from a starting value, thus stimulating the exploration of the PSO. We consider two possible starting values, 0.9 and 0.7, and two possible slopes, $0.6/Niter$ and $0.2/Niter$, which should allow to analyse the behaviour of the PSO with either more exploration or more exploitation in the last iterations. In consequence, $w$ will be linearly decreasing in four possible intervals, as shown in Table 1. Regarding the guiding probabilities, $p_1$ and $p_2$, since their sum must be less or equal to 1, we consider them as a single factor: given the values 0.7, 0.5, 0.3 and 0.1, $p_1$ and $p_2$ simultaneously traverse these values in increasing and decreasing order respectively, that is, first $p_1=0.7$ and $p_2=0.1$, then $p_1=0.5$ and $p_2=0.3$ and so forth. Thus, we always ensure that the constraint $p_1 + p_2 \le 1$ holds, while covering a varied sample of values for both probabilities. Finally, for the delay parameter we consider the two extremes values, $\delta = 0$—which in the deterministic case restricts the search to the space of non-delay schedules—and $\delta =1$, together with two intermediate values $\delta = 0.25$ and $\delta = 0.75$.

Table 1 Parameter settings

With a total of four parameters and four factor levels each, the orthogonal array $L'_{16}$ is pertinent for the Taguchi analysis. For every combination of parameter values given by the orthogonal array we run the PSO with the four multiobjective functions: $L(C_{max},AI_{av})$, $L(C_{max},AI_{min})$, $L(AI_{av},C_{max})$, and $L(AI_{min},C_{max})$ on a fuzzy instance of each $8 \times 8$ problem.

To measure the quality of each configuration we need a value that can consistently combine such heterogeneous values as $C_{max}$, $AI_{av}$ and $AI_{min}$ while taking into account the lexicographical goal programming nature of the model. First, we consider the distance of each value to its corresponding target, averaged across ten runs of the algorithm and normalised so as to unify scales (notice that such distance is taken to be zero if the target is reached). Let $d_1$ and $d_2$ denote, respectively, the normalised distance values for the primary and secondary objective. These values will allow us to characterise the algorithm’s performance for the Taguchi analysis as follows: if the first target is reached, i.e. $d_1=0$, then the performance is given by $d_2$ (the distance to the second objective); in the worse case that the primary objective does not reach its target ($d_1 >0$), then the performance is given by $1+d_1$. Since $0 \le d_2 \le 1$, this guarantees that the algorithm is always considered to perform worse when the target for the primary objective is not reached, as well as discriminating among solutions taking into account how far they are from reaching each target. We have opted for using this performance measure directly, instead of the classical signal-to-noise ratio, in the line of the use of the Taguchi method in Jia and Seo (2013) and Wang et al. (2013) for scheduling problems.

Table 2 shows, for every combination of factor levels in the orthogonal array, the average performance value for each of the four multiobjective functions considered. It is based on these values that we can compute the response value of each parameter and analyse their significance rank. As a summary, Fig. 2 depicts the response values of each parameter for each of the four objective functions, illustrating the effect of the parameter levels on the algorithm’s performance. Clearly, the most significant parameter for all objective functions is $\delta$, with a difference between the highest and lowest level over 1.25 of a maximum possible difference of 2.00 (see Fig. 2d). The second most significant parameter is the pair of guiding probabilities (Fig. 2c), although their effect is significantly smaller. Finally, the smallest effect on the performance for all functions is obtained with the swarm size and the inertia weight (see Fig. 2a, b). Additionally, for the two most significant parameters it can be clearly seen that the best level remains the same for all four objective functions. This is not the case for swarm size and inertia weight, where the best levels differ for $L(C_{max},AI_{av})$ and $L(AI_{av},C_{max})$; however, the difference is relatively small, 0.079 for swarm size and 0.142 for inertia weight. In consequence, we will take the factor level that performs best for all but one objective functions, this being a good value in all cases.

Fig. 2

Average performance of the four multiobjecive-PSO for each parameter level. a Swarm size $(N)$. b Inertia weight $(w)$. c Guiding probabilities $(gp)$. d Delay parameter $(\delta )$

Table 2 Orthogonal tabulation and average performance values

As a result of this analysis, the parameter setting in what follows will be $\delta = 0.25$, $gp = (p_1, p_2) =(0.7, 0.1)$, $w$ linearly decreasing from 0.7 to 0.1, and swarm size $N = 80$ for all objective functions.

Highest priority for makespan minimisation

Let us first consider the case where $C_{max}$ is the objective with highest priority and let $L(C_{max},AI_{av})$ and $L(C_{max},AI_{min})$ denote the resulting multiobjective functions for $AI_{ag}=AI_{av}$ and $AI_{ag}=AI_{min}$ respectively.

In order to illustrate the algorithm’s convergence, we first focus on a single problem instance. Figure 3 shows the convergence pattern of $L(C_{max},AI_{min})$ for a fuzzy instance generated from J8-per20-1, one of the largest and hardest instances. We can see how the algorithm shows a proper convergence: initially the algorithm minimises the expected makespan $E[C_{max}]$ while the behaviour of $AI_{min}$ is erratic. However, once the algorithm has reached the expected makespan target (around the 250th iteration), it starts maximising $AI_{min}$ instead. We can also observe the evolution of the $AI_{av}$ value and its correlated behaviour w.r.t. $AI_{min}$. Analogous convergence curves show that the number of iterations can be reduced for $7 \times 7$ to 2,100 iterations.

Fig. 3

Evolution of $E[C_{max}]$ and $E[AI_{min}]$ on the $L(C_{max},AI_{min})$ version for the J8-per20-1 instance

Tables 3 and 4 contain a summary of the results obtained when makespan minimisation has the highest priority. For each objective function used by the PSO they report the values of $E[C_{max}]$, $AI_{av}$ and $AI_{min}$ in the solution, averaged across the 30 executions of the PSO and the 10 fuzzy instances generated from the same original problem, together with the standard deviations. The average values are shown in bold when they reach the target for the corresponding objective.

Table 3 Comparison of results for $E[C_{max}]$ highest priority on instances of size $7 \times 7$

Table 4 Comparison of results for $E[C_{max}]$ highest priority on instances of size $8 \times 8$

A first look at Tables 3 and  4 confirms the strong correlation between the values of $AI_{min}$ and $A_{av}$, both measuring the overall due-date satisfaction. In most cases, the single-objective version using any of these aggregated values reaches the target value established for the other aggregated measure. That is, when any one of these aggregated measures is optimised, the alternative one is also optimised.

Let us now compare results obtained by the proposed multiobjective approach using $L(C_{max},AI_{min})$ and $L(C_{max}, AI_{av})$ with the results obtained when optimising a single criterion. For the objective with the highest priority—minimisation of expected makespan—we see that both multiobjective approaches behave similarly to the single-objective function. In particular, they always reach the expected makespan target. Additionally, the multiobjective approach obtains a clear improvement in due-date satisfaction. Indeed, for all instances, $AI_{min}$ values obtained with $L(C_{max},AI_{min})$ are in average 159 % better than those obtained using $E[C_{max}]$ as single-objective function. There are however remarkable differences in the improvement rate depending on the instance type. For example, due-date satisfaction improves only 8 % for J7-per10 instances and 16 % for J8-per10, but this improvement scales up to 164 and 450 % in per20 instances of sizes $7\times 7$ and $8\times 8$ respectively. This variability is due to the fact that, as mentioned above, the dependency between $E[C_{max}]$ and $AI_{min}$ is greater for per10 instances, given the way in which the original benchmark was created. In consequence, for per10 problems, when the makespan is optimised, due-date satisfaction is also being optimised to a certain extent; however this is not always the case for an arbitrary open shop problem.

Regarding $AI_{av}$ values, they improve 7.2 % when using $L(C_{max},AI_{av})$. Again there is a remarkable variability in the improvement depending on the family of problems: 2.1 % for per10 instances and 12.2 % for per20 instances. It is also tempting to conclude that the gain obtained with $L(C_{max},AI_{min})$ is much higher than that obtained with $L(C_{max},AI_{av})$. However, this is only a scale effect. If instead of considering absolute gains, we measure the reduction of the gap between the $AI_{min}$ and the $AI_{av}$ values and their corresponding targets, the multiobjective approach $L(C_{max},AI_{min})$ is in average over 36 % better than $E[C_{max}]$ and $L(C_{max},AI_{av})$ is also over 36 % better than $E[C_{max}]$ w.r.t. the corresponding secondary target. In any case, it is worth noticing that for per10 instances $L(C_{max},AI_{min})$ performs better than $L(C_{max},AI_{av})$ whereas for $per20$ instances the best performance corresponds to $L(C_{max},AI_{av})$ in terms of gap reduction w.r.t. its secondary target. A possible explanation is that $AI_{min}$ is a more demanding aggregation operator. If it is relatively “easy” to satisfy the due dates for all jobs (at least to a certain extent), then $0<AI_{min} \le AI_{av}$ and $AI_{min}$ will probably provide a better guide for maximising due date satisfaction. However, as long as it is likely that one of the due dates is not satisfied at all in schedules with good makespan values (as is the case for per20 problems), then $AI_{min}=0$ with high probability, thus providing a poor guide for the optimisation process.

Finally, the correlation between both aggregation operators is further confirmed if we look at the behaviour of $AI_{av}$ in case of $L(C_{max},AI_{min})$ and $AI_{min}$ in case of $L(C_{max},AI_{av})$: both multiobjective approaches significantly reduce the alternative due-date objective, with a gap-improvement of approximately 26 % in both cases.

Let us now compare the multiobjective PSO using $L(C_{max},AI_{av})$ or $L(C_{max},AI_{min})$ with the single-objective memetic algorithm (MA) from González Rodríguez et al. (2010) in terms of expected makespan minimisation. Table 5 contains the expected makespan results for each method—MA optimising only $E[C_{max}]$, PSO with $L(C_{max},AI_{av})$ and PSO with $L(C_{max},AI_{min})$—with values averaged across the 10 instances of each size and 30 runs of the algorithm. Clearly, the PSO with both multiobjective functions $L(C_{max},AI_{av})$ and $L(C_{max},AI_{min})$ compares favourably with the single-objective MA in terms of makespan values. Indeed, the multiobjective PSO reduces $E[C_{max}]$ values about 2.25 % (slightly over 3 % for per10 instances and slightly below 1.5 % for per20 instances), with no significant differences between different problem sizes or different aggregated measures for due-date satisfaction. This reduction may not seem very important in absolute values. However, on a closer look we can see that the MA never reaches the expected makespan target value, whereas the multiobjective PSO reaches this target in all instances. We can conclude that our multiobjective PSO outperforms the previous single-objective algorithm when it comes to optimising the objective with the highest priority (makespan), while also optimising the secondary objective.

Table 5 Comparison between PSO and MA in terms of $E[C_{max}]$

Highest priority for due-date satisfaction

We now consider the alternative priority structure where due-date satisfaction becomes the primary objective; let $L(AI_{ag},C_{max})$ denote the resulting lexicographic goal programming multiobjective function. If we now compare each $L(AI_{ag},C_{max})$ with the corresponding aggregated due-date satisfaction value $AI_{ag}$ ($AI_{min}$ or $AI_{av}$), the results are analogous to the case where makespan was the first objective. In all instances $L(AI_{ag},C_{max})$ reaches the corresponding target for due-date satisfaction value whereas the gap between the expected makespan and its target value is reduced 36 % in average when $AI_{ag} = AI_{min}$ and 40 % in the case that $AI_{ag} = AI_{av}$. Figure 4 shows the $E[C_{max}]$ values (averaged across the 10 fuzzy instances of every original problem and the 30 executions of the PSO algorithm) obtained with $AI_{min}$, $AI_{av}$ and the corresponding multiobjective functions on each family of problems. It also depicts the $E[C_{max}]$ target values for each family. We can clearly appreciate how the expected makespan behaves better in the multiobjective approach. We can also observe that $AI_{av}$ used as single objective function obtains in general slightly better $E[C_{max}]$ values than the alternative $AI_{min}$. Also, its multiobjective counterpart $L(AI_{av},C_{max})$ performs slightly better (in terms of makespan minimisation) than $L(AI_{min},C_{max})$. The explanation, again, lies in the fact that $AI_{min}$ is a more pessimistic aggregator of individual job due-date satisfaction. The figure also illustrates that, as above, the solutions are in general closer to the target values for per10 instances than for per20 ones.

Fig. 4

Average $E[C_{max}]$ values obtained with $AI_{min}$, $AI_{av}$ and the corresponding multiobjective $L(AI_{min},C_{max})$ and $L(AI_{av},C_{max})$

Conclusions and future work

We have proposed a multiobjective approach for solving the open shop scheduling problem with uncertain durations and flexible due dates modelled using fuzzy sets. We have adopted a lexicographic goal programming framework to deal with the multiple objectives of minimising the project’s makespan and maximising due-date satisfaction. The resulting problem has been solved by adapting a particle swarm optimisation algorithm to the hierarchical multiobjective framework. The experimental results, on fuzzy instances of well-known benchmark problems, illustrate the potential of our proposal. In general, the multiobjective approaches perform as well as their single-objective counterparts when it comes to optimising the objective with the highest priority, reaching the target levels in all cases. Additionally, the multiobjective approaches greatly improve on the secondary objective. Also, the multiobjective PSO algorithm compares favourably to a memetic algorithm from the literature in terms of makespan minimisation, when this is the objective with the highest priority.

In the future, we would like to contemplate an alternative approach to multiobjective optimisation, appropriate for the case when no priority structure among multiple objectives can or needs to be established. We would like to explore the known relationships between lexicographic and Pareto optimality, as well as extending the PSO algorithm to directly work with sets of non-dominated solutions. We would also like to adapt the PSO algorithm to other scheduling problems with uncertainty, such as job shop or resource-constrained project scheduling.