A General Local Search Pareto Approach with Regular Criteria for Solving the Job-Shop Scheduling Problem Multi-resource Resource Flexibility with Linear Routes

Abstract

The Job-shop Scheduling problem Multi-resource Resource flexibility with linear routes is an extension of the classical Job-shop Scheduling problem “JSMRFLR” where an operation needs several resources (machines) simultaneously to be processed and each machine is selected from a given set. Linear route indicates that an operation is exclusively performed for a job. Publications related to this problem are really scarce and they are dedicated to minimize makespan criterion, which aims to minimize the use of the machines. In the modern scenery of the Operations Management, the exclusive minimization of the makespan does not allow to analyze aspects of the customer service to ensure high levels of competitiveness such as the consideration of due-date and the importance between jobs. In this paper, we propose a general Pareto approach to solve the JSMRFLR with regular criteria, which operates by an efficient local search at using a fast estimation function for the criteria considering the conjunctive graph. During the search, the set of non-dominated solutions is updated. The efficiency of our approach is illustrated on instances of literature at performing three sets of criteria. The first set considers makespan and maximum tardiness. In the second total flow time is added and in the third the total tardiness. As a product of our approach, a reference of results is proposed by future research.

1 Introduction

For the Operations Management, the success of the production programming depends on the scheduling decisions. These decisions lead to determine the sequence of activities and the assignment of resources to optimize an objective function. In the literature of scheduling, the highest rigor of the decisions have been focused on configurations derived of the classical flow-shop and Job-shop problems such as parallel machines, sequence dependent set up times, maintenance activities and others. Concerning to the minimization of criteria, makespan, that is the maximum completion time of jobs has been the most studied. Minimizing makespan does not consider relevant aspects for the customer service like the due-date of jobs that represents the delivery date agreed with customers and the importance between them. Therefore, minimizing regular criteria different than the makespan leads to identify key aspects to improve the customer service.

One of the extensions of the Job-shop problem is the Multi-resource and Resource flexibility with linear routes. This extension was proposed by [1]. The Multi-resource considers that an operation needs several resources simultaneously to be performed and resource flexibility determines that a resource (machine) is chosen from a given set. Linear route means that each operation is performed exclusively for a job. To best of our knowledge, it is scarce the level of publications at solving this problem even considering makespan.

This paper is oriented to improve the level of customer service and the productivity in a more realistic industrial environment such as the Job-shop Scheduling Problem Multi-resource Resource Flexibility with linear routes “JSMRFLR”. To reach the goal, a fast local search algorithm that uses the properties of a conjunctive graph adapted to regular criteria is designed to solve the JSMRFLR in Pareto manner at minimizing a combination of regular criteria. The solutions that belong to the Pareto front are gotten iteratively. In each iteration, a random criterion is selected and the move is determined by an estimation function that considering the evaluation simultaneous of reversing a critical arc ($x,y$) that belongs to the critical path of a job that affects a criterion and the reassignment of $x$ and $y$ at maintaining the level of operations into the conjunctive graph (maximum number of arcs from the start dummy node) between operations $j$ and $k$.

During the search, the set of non-dominated solutions is updated at removing the dominated solutions and adding of a new one if it is necessary. The proposed approach is validated in instances of the literature proposed by [1] at solving three different sets of criteria. In the first set, makespan and maximum tardiness are solved. The second set adds the total flow time, and the third adds the total tardiness. As a contribution of our experiments a benchmark of results is proposed for future research. The paper is detailed as follows. Section 2 describes and models the problem with the considerations of the front of Pareto. In Sect. 3, the algorithm that solves the problem is described. Finally, Sect. 4 illustrates some computational experiments.

2 The Problem and Pareto Optimization

The objective of this Section is to illustrate the problem with its components and the guidelines to obtain the Pareto front at minimizing a set of regular criteria.

2.1 Problem Description and Modeling

To describe the problem, it is necessary to consider the Job-shop Scheduling Problem “JSP”. In the JSP, a set of n jobs $J = \left\{ {J_{1} , \ldots .J_{n} } \right\}$ are processed on a set $M = \left\{ {M_{1} , \ldots .M_{m} } \right\}$ of m machines that are available. Each machine can only process one job at a time. A job $J_{i}$ is obtained at performing sequentially $n_{i}$ operations in a fix route. Preempting operations is not allowed. It means that an operation cannot be interrupted once started. Each job $J_{i}$ has a due-date $d_{i}$. The JSP Multi-resource Resource Flexibility with linear routes “JSMRFLR” considers that an operation needs several resources simultaneously to be performed and resource flexibility indicates that a resource may be selected in a given set.

A model of the disjunctive graph for the Multi-resource shop scheduling with resource flexibility considering linear and non-linear routes is proposed in [1]. This model is used for minimizing makespan. To minimize regular criteria in the JSMRFLR, we have added the properties of linear routes from the JSP, which were validated in [2] and adapted for the flexible Job-shop scheduling problem in [3]. In the conjunctive graph for minimizing regular criteria for the JSMRFLR, the n nodes $\phi_{i}$ that represents the finalization of the jobs, the concept of maximum number of arcs between node $0$ and an operation $x$ ($l_{x}$) and the tail from a node $x$ to the dummy node $\phi_{i}$($q_{x}^{i}$) have been added.

In the JSMRFLR, the disjunctive graph is noted $G = \left( {V,A,E} \right)$, where $V$ is the set of nodes, $A$ is the set of conjunctive arcs and $E$ is the set of disjunctive arcs. The nodes in $E$ represent operations of jobs (set $O$), plus a dummy node 0 that corresponds to the start of each job, and n dummy nodes $\phi_{i}$. $A$ contains conjunctive arcs which connect two consecutive operations on the routing of jobs, the node 0 to every first operation of each job, and the last operation of $J_{i}$ to a dummy node $\phi_{i}$. The set $E$ contains disjunctive arcs between every pair of operations assigned to the same resource. Let $E_{k}$ be the set of disjunctive arcs between pairs of operations that must be processed on $k$, $E = \cup E_{k}$.

The set of operations $O$ has to be processed on a set of machines (resources) M. To be processed an operation $x \in O$ requires $R\left( x \right)$ resources simultaneously and $M_{x}^{k}$ is the resource subset in which the $k^{th}$ resource ($1 \le k \le R\left( x \right)$) must be selected. The $M_{x}^{k}$ subsets are not necessarily disjoint, for example, a resource could belong to several subsets. To obtain a feasible schedule in the JSMRFLR, assignment and sequencing decisions have to be made to solve the conflict in $E$. In each operation, the assignment decision consists on determining which machine or resource must be selected from each subset to perform it. However, it is mandatory to ensure of not assigning a resource twice or more to the same operation, additionally the processing time of an operation $x$ $(p_{x} )$ is determined by the maximum time of the resource where it is assigned. The sequencing decision deals with determining a sequence of operations on each selected resource $k$ to minimize any regular criterion. It is important to highlight that the sequence of operations on resources does not lead to create cycles in the conjunctive graph. As soon as a solution is obtained, it is possible to extract information to identify the properties to create moves which lead to improve any criterion. The arc from 0 to the first operation of ${\text{J}}_{\text{i}}$ has a length equal to the release date $r_{i}$ of ${\text{j}}_{i}$. Any remaining arc has a length equal to the processing time of the operation from which it starts. The starting time of $x$, ${\text{h}}_{x}$ = $L\left( {0, x} \right)$ called head, that corresponds to the length of the longest path from 0 to $x$. The tail from a node $x$ to the dummy node $\phi_{i}$($q_{x}^{i}$) is equal to [$L\left( {x, \phi_{i} } \right) \,{-}\,p_{x}$] if a path exists from $x$ to $\phi_{i}$ and $- \infty$ otherwise. A path from 0 to $\phi_{i}$ is called critical if its length is equal to ${\text{C}}_{\text{i}}$, and every node $x$ belonging to this critical path is critical according to job ${\text{J}}_{\text{i}}$. A critical node $x$ for job ${\text{J}}_{\text{i}}$ satisfies $h_{x} + p_{x} + q_{x}^{i}$ = ${\text{C}}_{\text{i}}$. The level $l_{x}$ of a node $x$ in $G$ denotes the maximum number of arcs in a path from 0 to $x$. After obtaining the heads of the nodes of the graph, the criterion of a feasible schedule represented by the selection can be determined in $O\left( n \right)$ from the starting times of the dummy nodes. For instance, the makespan is obtained using the formula $C_{max} = \hbox{max} C_{i}$. Additionally the tardiness $(T_{i} ),$ $T_{i} = \hbox{max} \left( {0, C_{i} - d_{i} } \right).$ Then, the maximum tardiness is $T_{max} = \hbox{max} T_{i}$, total tardiness ($T$) is the sum of the tardiness of jobs ($\sum\nolimits_{1}^{n} {T_{i} }$) and the total flow time is the sum of the completion time of jobs ($\sum\nolimits_{1}^{n} {C_{i} }$).

2.2 Pareto Optimization

Pareto optimization aims to find a set of non-dominated solutions at optimizing a set of criteria (often conflicting). In our case, for optimizing regular criteria, all objectives lead to be minimized. The set of non-dominated solutions $Q$ represents the Pareto front and its comprehension requires to check the dominance between solutions, and the conditions that a solution $s$ must satisfy to be included in $Q$. Concerning to the dominance between solutions, solutions $A$ and $B$ are considered. To determine if $A$ dominates to $B$ or $B$ is dominated by $A$, the following conditions must be true: (1) $A$ is not worse than $B$ for all objectives, and (2) $A$ is strictly better than $B$ for at least one objective. To know if a solution $s$ must be included in $Q$, two conditions must be ensured: (1) Any two solutions of $Q$ must be non-dominated with respect to each other and, (2) Any solution not in $Q$ is dominated by at least one solution in $Q$.

The Fig. 1 helps to illustrate two non-dominated solutions of an instance with three jobs, seven operations and six machines or resources ($M_{1}$, $M_{2}$, $M_{3}$, $M_{4}$, $M_{5}$ and $M_{6}$) at minimizing makespan and maximum tardiness simultaneously. Besides, the due dates for jobs are determined. They are $d_{1} = 6, \,d_{2} = 12$ and $d_{3} = 6$ (see column $d_{i}$). The solution in Fig. 1(a) aims to minimize makespan, and in the Fig. 1(b) the maximum tardiness. The solution in the Fig. 1(a) can be used to explain some properties of the conjunctive graph and some remarks can be extracted. The first job has two operations (see the first route for a job). The first operation of the first job requires two resources simultaneously (see dashed rectangle). The first resource is selected between $M_{1}$ and $M_{4}$. If $M_{1}$ is selected 3 is the processing time, otherwise 2. The second resource is selected between $M_{2}$ and $M_{4}$. In this example, $M_{4}$ and $M_{2}$ are assigned respectively (they are highlighted in yellow and blue color) and the processing time is 2. Note that a resource was not assigned twice. Considering the same operation, it starts at time 0 and finishing at time 2 (see 0/2), since the processing time is 2 (see 0 + 2 = 2). Considering that one operation cannot start before finishing all its predecessors, the completion time of all jobs (see column $C_{i}$) and the tardiness of all jobs are calculated (see column $T_{i}$).

Fig. 1.

Examples of two non-dominated solutions with makespan and maximum tardiness

The solutions illustrated in the Fig. 1 are non-dominated solutions. If for example makespan and maximum tardiness are considered, in the Fig. 1(a) the values for the criteria are 12 and 4 respectively, and in the Fig. 1(b) these values are 14 and 2. It means that for a decision maker without considering importance between criteria both solutions are equivalent and they satisfy the conditions of non-dominance between solutions.

2.3 Quality of the Pareto Front

There is not any consensus to establish the quality of the Pareto Front. Different approaches have been proposed (see for example [4] and [5]). However, two aspects are mandatory to consider: convergence and diversity. Convergence implies that the set of non-dominated solutions must be located closest to the origin of coordinates. Diversity is related to the solutions in sparsely space to ensure that the decision maker has several and representative trade-off solutions among conflicting criteria. To determine the quality of the front, the set of metrics employed in [5] are analyzed. In this case, for the convergence the hypervolume ($HV$), elite solutions and the Mean Ideal Distance ($MID$) are measured. $HV$ is the volume covered by the solutions of the front and respect to the worst solution, since regular criteria are minimized. Elite solutions are the best values of the criteria. $MID$ is the average Euclidean distance obtained between each non-dominated solution and the origin. Concerning to the diversity, the maximum spread ($D$) and spacing ($SP$) are analyzed. $D$ is the longest diagonal of the hyper box formed by the extreme values of the criteria, and $SP$ is the average distance between consecutive solutions.

The Fig. 2 is an image of the results generated by our algorithm, which will be explained in the next section at minimizing in Pareto manner makespan, maximum tardiness and total flow time (TFT) at performing the instance mjs07 during five minutes from [1]. This Figure is divided in two parts. The part a represents a txt file with the results. For example, the algorithm gets eight non-dominated solutions. Each solution shows the value of the criteria. Additionally, the metrics are separated by diversity and convergence. In the part b, the eight non-dominated solutions are plotted on a three dimensional plane.

Fig. 2.

Results for the instance mjs07 at minimizing $C_{max}$, $T_{max}$ and $\sum C_{i}$

3 Description of the Algorithm

In Sect. 2 were defined the components of the problem JSMRFLR and the guidelines of Pareto optimization, which are used to describe the proposed algorithm. Basically, our algorithm is a local search process that uses the properties of the conjunctive graph, a test of feasibility conditions, an estimation function and a procedure to update the set of non-dominated solutions.

3.1 Feasibility Conditions and Estimation Functions

Feasibility conditions aim to check if a critical operation could be moved without performing any transformation in the conjunctive graph. For this problem, two types of moves are considered: reversing critical arc ($x,y$) and the reassignment of a critical operation performed on resource $L$ to resource $L^{\prime}$ between $j$ and $k$. Respect to reverse critical arcs, the conditions validated in [2] for minimizing regular criteria have been extended to this problem. However, it is important to clarify that if several arcs connect $x$ and $y$, all arcs must be reversed, since they are critical, and $x$ and $y$ must belong to different jobs.

In the reassignment, moving an operation $\varepsilon$ ($\varepsilon = x$ or $\varepsilon = y$) between operations $j$ and $k$ from resource $L$ to $L^{\prime}$, it is necessary to check that there are no paths from $b \left( {\forall b \in B} \right)$ to j, and simultaneously from $k$ to $c \left( {\forall c \in C} \right)$. Here, $B$ (resp. $C$) is the set formed for all immediate successors (resp. predecessors) of $\varepsilon$ without considering the successor (resp. predecessor) linked to the resource $L$. To ensure it, two expressions considering the number of arcs must be satisfied: (1) $l_{j} \le { \hbox{min} }_{{{\text{b}} \in {\text{B}}}} \{ l_{b}$} and (2) $l_{k} \ge { \hbox{max} }_{{{\text{c}} \in {\text{C}}}} \{ l_{c}$}. These expressions are validated, since there is not possible to get a path from a node $u$ to $v$ if $l_{v} \le l_{u}$. To estimate the value of any regular criterion, the completion time of a job must be estimated. It means to determine the completion time of each node $\phi_{i}$. To determine it, two sets of functions based on the type of move. Concerning to swap a critical arc, the three expressions to $L_{1}$, $L_{2}$ and $L_{3}$ from [2] have been extended to the JSMRFLR problem. Those expressions aim to maintain the same values for the heads or start time for operations and the tails to nodes $\phi_{i}$ at reversing a critical arc. At reassigning an operation $\varepsilon$ between $j$ and $k$, we want to maintain the same conditions (heads and tails) to reach a better precision of the estimation. In this case the condition for $C_{1}$, $C_{2}$ from [1] and $L_{3}$ from [6] have been adapted at considering regular criteria.

3.2 Steps of the Search

The search starts with an initial solution, which is the first solution added to the set of non-dominated solutions. Then, iteratively two steps (improvement and diversification) according to the conditions of the graph are executed. Simultaneously the set of non-dominated solutions is updated. In the initial solution, the jobs are sorted in increasing way according to their due-date. Then, for the assignment and sequence of operations on machines (resources) is solved at considering the operation in route of the order jobs. It means that, if there exist and ordering of jobs, the assignment and sequence decisions solve the first operation of all them, then, the second and so on. The objective of the assignment and sequence decisions aim to obtain the lowest completion time per operation at evaluating the capacity of machines. The initial solution is general and it does not make any distinction between criteria.

To transform the conjunctive graph, all critical arcs that belong to the critical paths of jobs that affect the criterion are referenced to create a move at selecting the best neighbor. The algorithm aims to optimize a Pareto approach and iteratively a random criterion is selected to create a move. Selecting the best neighbor implies determine the feasibility of all moves, and then on each feasible move the evaluation of the estimation function which were described in Sect. 3.1. To clarify the functioning of the search, let CRT be a set of k criteria to minimize, $Crt_{i } \in$ CRT a criterion i to minimize; besides, let $\varvec{C}_{{\varvec{Sel}}}$ be a random chosen criterion to optimize from CRT. Let $CFOR \subset CRT$ be a subset of CRT that contains the forbidden criteria, which means that in case of a random selection of a criterion, a forbidden criterion cannot be selected. A criterion becomes forbidden when, in the improvement step, it is selected to create a move, and it cannot be generated.

The Fig. 3 illustrates the algorithm for the improvement step. In each iteration, a random criterion $\varvec{C}_{{\varvec{Sel}}}$ is selected to create a move. If it is not possible to create a move using $\varvec{C}_{{\varvec{Sel}}}$, $\varvec{C}_{{\varvec{Sel}}}$ becomes forbidden and it is added to CFOR. The search selects a new criterion that belongs to CRT-CFOR. However, when a move is performed, all criteria are authorized to be selected or the set CFOR is emptied. If it is not possible to create a move, the search goes to the diversification step considering the neighborhood of the last forbidden criterion. In this step, when a move is performed the criteria with its local and global optimal are updated.

Fig. 3.

Algorithm for the improvement step

When, it is not possible to create a move considering the random criterion, a new criterion is selected until the move can be performed. If an improvement move cannot be created, the diversification step starts. It consists on performing iteratively b random moves (b $\in$ [2, 5]) considering the last selected criterion. After that, the search returns to the improvement phase. The set of non-dominated solutions is updated as follows. When a solution $s$ is gotten, it is checked to determine its addition in $Q$ at applying the conditions described in Sect. 2.2. If $s$ were added in $Q$, $s$ could dominate other solutions, which must be removed from $Q$. The set of non-dominated solutions is updated at validating simultaneously the addition of the new solution and the elimination of the dominated solutions.

4 Computational Experiments

To validate and evaluate the efficiency of our approach, the instances with linear routing studied in [1] have been considered. Our algorithm was developed in Java language. The experiments were conducted on a PC with 3.40 GHz and 8 GB RAM for each set of criteria on each instance during ten minutes. To calculate the maximum tardiness and the total tardiness, it is necessary to determine the due-date $d_{i}$ of the jobs. They were generated by introducing a parameter $f$ equals to 1.1, which is inspired from [7]. $d_{i}$ is determined by multiplying the sum of the average processing times of operations belong to $J_{i}$ by $f$. To determine the average processing time of an operation, it is calculated at considering the highest processing time per subset of resources. It is important to mention that $d_{i}$ was rounded to the next integer number.

The results are presented in three steps. In the first step the efficiency of makespan criterion is evaluated at considering the best known values determined in [1]. In the second step, the elite solutions are analyzed to determine the best combination of criteria to optimize and finally, with the best combination of criteria the results for the metrics of the front of Pareto are calculated.

4.1 Evaluating Makespan

Makespan criterion is the only benchmark to determine the quality of our results at evaluating its convergence. It means the nearest distance respect to a known value. The Table 1 illustrates the best known values (see column $BKV$) and the best values at considering the three sets of criteria. Additionally, column $DP\left( \% \right)$ determines the percentage difference between the best result and the best known value. Besides, if a better known value is gotten, it is underlined and an asterisk is written in column $DP\left( \% \right)$. The best makespan of our experiment are written in bold.

Table 1. Results for the best makespan in the three sets

At observing the Table 1, it is possible to infer that our approach evidences a significant performance at minimizing the makespan combined with other criteria. For example, our approach leads to a better makespan than the best known value in nine of 68 instances (mjs02, 06, 11, 12, 15, 17, 19, 24 and 26). Besides, the best known value is reached in three instances: mjs01, mjs40 and mjs42, since, the percentage difference is 0.0 (see column $DP$). Additionally, in 16 instances the $DP$ is less or equal than 5.0% and in six of them is less than 1.0%. Respect to each set, $Set A$ Performs better than $Set B$ and $Set C$ in 52 instances. $Set C$ performs better in 16 instances and $Set B$ in eight without a superiority level. Since, in the eight instances $Set B$ gets the same performance than $Set C$. As conclusion, at evaluating the convergence of the makespan in the consolidation of the set of non-dominated solutions $Set B$ is not efficient and the better combination is the maximum tardiness.

4.2 Evaluating Maximum Tardiness and Total Flow Time

The Table 2 illustrates the elite solutions for both criteria. Again, the best value for the criteria is written in bold. Analyzing the results for maximum tardiness, in 32 instances, optimal solution (${\text{T}}_{ \hbox{max} } = 0)$ is gotten, and in 25 of them is gotten in the three sets for the three sets. Concerning to the performance of the sets, ${\text{Set A}}$ presents the best performance in 29 instances, ${\text{Set B}}$ in 5 and ${\text{Set C}}$ in 15. Respect to the total flow time, only ${\text{Sets B}}$ and ${\text{C}}$ are analyzed. At observing the results, ${\text{Set C}}$ leads to better results, since, it is evidenced in 58 instances. At evaluating the performance of the three sets, it is evident the superiority of the $Set B$ when a bi-criteria analysis (Makespan and Tmax) is performed. However, if some criteria are added, the best results are gotten in $Set C$.

Table 2. Results for the best $T_{max}$ and $\sum C_{i}$ in the three sets

4.3 Results for Set A and Set C

The main conclusion of the last sub Sections is that the best results are reached for $Sets$ $A$ and $C$. In this Section the results of the metrics are calculated and written in Tables 3 and 4, where column Sol means the number of non-dominated solutions generated by the search. Additionally, in Table 4 the total tardiness criterion is recorded. The results of these Tables can be used as benchmark to determine the quality of a Pareto front. However, different combination of criteria must be performed to determine the performance mainly of the makespan at trying to reduce the distance from the origin.

Table 3. Quality metrics for $Set\,A$

Table 4. Quality metrics for $Set\,C$

5 Conclusion

This paper illustrates a local search algorithm to solve the job shop scheduling Multi resource Resource flexibility with linear routes at minimizing different combinations of regular criteria in Pareto manner. We have presented results for three sets of criteria. To best of our knowledge, there is not any reference about of this extension of the job-shop scheduling problem to calculate regular criteria different than the makespan. The algorithm is supported in the adaptation of estimation functions as extensions of the classical problem and the proposition of a conjunctive graph. In its formulation, the properties of heads, tails and levels of operations have been considered. Computational results show the efficiency of our algorithm at getting some best known values and better values in some instances for the makespan. Additionally optimal solutions are gotten by the maximum tardiness and the total tardiness.

As perspective of the proposed approach, we will study two extensions. The first is the formulation of new estimation function for non-linear route problem (for example, in assembly process), and the second is the solution considering weighted objective functions for improving the making decision process. This research is supported by the project “Formulation and validation of heuristics for optimizing the customer service in flexible configurations in the Tolima region”, identified with the code 17-465-INT, which is financed by the Universidad de Ibagué (Colombia).