# Job Shop Scheduling with Alternative Machines Using a Genetic Algorithm Incorporating Heuristic Rules
## -Effectiveness of Due-Date Related Information-

Parinya Kaweegitbundit, Toru Eguchi

► To cite this version:

Parinya Kaweegitbundit, Toru Eguchi. Job Shop Scheduling with Alternative Machines Using a Genetic Algorithm Incorporating Heuristic Rules -Effectiveness of Due-Date Related Information-. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2015, Tokyo, Japan. pp.439-446, 10.1007/978-3-319-22756-6_54 . hal-01417529

HAL Id: hal-01417529

https://hal.science/hal-01417529

Submitted on 15 Dec 2016

**HAL** is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Job Shop Scheduling with Alternative Machines Using a Genetic Algorithm Incorporating Heuristic Rules
## -Effectiveness of Due-date Related Information-

Parinya Kaweegitbundit and Toru Eguchi

Graduate School of Engineering, Hiroshima University, Japan
eguchi@hiroshima-u.ac.jp

**Abstract.** This paper deals with an efficient scheduling method for job shop scheduling with alternative machines with the objective to minimize mean tardiness. The method uses a genetic algorithm incorporating heuristic rules for job sequencing and machine selection. Effective heuristic rules for this method have been proposed so far. However due-date related information has not been included in the heuristic rule for machine selection even though the objective is to minimize mean tardiness. This paper examines the effectiveness of due-date related information for machine selection in this method through numerical experiments.

**Keywords:** Job shop scheduling, alternative machines, tardiness, heuristic rule, genetic algorithm

## 1 Introduction

This paper deals with an efficient scheduling method for job shop scheduling with alternative machines. Some research papers related to this problem have been proposed in the literature [1][2]. In this problem, the machine for processing each operation is not fixed only one; there can be alternative machines. Not only the sequence of jobs on machine, but also the machine which process each operation must be selected for this scheduling. We have already proposed a scheduling method using a genetic algorithm incorporating heuristic rules [3][4]. In this method, heuristic rules for job sequencing and machine selection are embedded in the search of genetic algorithm. The performance of scheduling is improved using the knowledge of the rules. The rules for job sequencing are used when a machine became idle and there are multiple waiting jobs to be processed on the machine. The rules give priority values for the waiting jobs and the job with the highest priority value is selected as the next job to be processed on the machine. The rules for machines selection are used when a machine finishes processing an operation of a job. The rule gives values for candidate machines to process the next operation of the job. We have examined various heuristic rules for incorporation when the objective of scheduling is to minimize mean tardiness. As a result, (SL/RPN)+SPT rule [5] performed best for job sequencing. (WINQ+RPT+PT)×PT rule [6] performed best for machine selection. Although the objective of scheduling is to minimize mean
tardiness, the machine selection rule does not include due-date related information. In this paper, we examine the effectiveness of considering due-date related information for machine selection rules. Numerical experiments are carried out to show the effectiveness of including the information.

## 2 Job shop scheduling with alternative machines

The scheduling problem considered in this paper is described as follows: Consider the job shop that consists of *R* work centers. Each work center $W_r (r \in \{1,2,..., R\})$ has $M_r$ machines. The operation to be processed in a work center is performed on one of the machines in the work center. Each Job $J_i (i=1,2,..., I)$ has $n_i$ operations {$o_{ij} (j=1,2,..., n_i)$} that are processed by the increasing order of the operation number *j*. The operation $o_{ij}$ is processed on a work center $W_{z_{ij}} (z_{ij} \in \{1,2,...,R\})$ and the routings of the operations through work centers are diverse. We assume that $W_{z_{ij} \neq W_{z_{i,j+1}}}$ for $j=1,..., n_i-1$. The processing time of the operation $o_{ij}$ on machine *k* ($k=1,2,..., M_{z_{ij}}$) is $p_{ijk}$. Operations cannot be interrupted (non-preemption). Each machine can process only one job at a time; each job can be processed only on one machine at a time. The objective of scheduling is to minimize the mean tardiness defined as follows:

$$T = \sum_{i=1}^{I} \max(0, C_i - d_i) / I \quad (1)$$

where $C_i$ and $d_i$ are the completion time and the due-date of job $J_i$, respectively.

## 3 Scheduling optimization using a genetic algorithm

In this chapter, the genetic algorithm used in this paper is described. In the genetic algorithm, each operation has a gene for job selection and genes for machine selection. The number of genes for machine selection is the same as the number of candidate machines which can process the operation. Each gene for machine selection is prepared for each candidate machine. Each gene for job selection and machine selection is coded as a real value between 0 and 1. The set of genes for all the operations of jobs corresponds to a chromosome.

Decoding is carried out using a feed-forward scheduling simulation in which the genes are considered as priority values for job selection and machine selection. When machine finishes processing an operation of a job, the job goes to the input buffer of one of the candidate machine which can process the next operation of the job. The machine which has the largest value of gene is selected as the next machine to process the next operation. When a machine became idle and there are multiple waiting jobs to be processed in the input buffer of the machine, one of the waiting job is selected and is started to be processed on the machine. The job with the highest value of gene is selected as the next job. By this method, when all the operations of jobs are completed, a schedule is obtained. The mean tardiness of jobs in the schedule is used for calculating the fitness. The individual which has the smaller mean tardiness is defined to have the higher fitness in this method.
An elite strategy is adopted in this paper. The best 20% of individual is copied to the next generation. The other 80% individuals are generated using crossover by randomly selecting two individuals from the current generation. In crossover, 30% genes are randomly selected from one individual and the other 70% genes are randomly selected from another individual. The rate of mutation is 1%. For the detail construction of this genetic algorithm, refer to the literature [5][7].

# 4 Genetic algorithm incorporating heuristic rules

## 4.1 Incorporation of heuristic rules

Although the genetic algorithm alone described in chapter 3 can search the optimal schedule, the performance is not good. The performance of scheduling can be improved by incorporating problem specific knowledge. Eguchi et al. have proposed the job shop scheduling method using a genetic algorithm incorporating a priority rule for job selection [7]. In this method, when decoding, a job is selected using not only the value of gene for job selection but also the value calculated by applying a priority rule. Specifically, the job with the highest value of the multiplication of the gene and the priority value calculated by the rule is selected as the next job to be processed. By this method, the knowledge of priority rule can be embedded in the search of genetic algorithm. As the same way, machine selection rules can be incorporated for machine selection. Specifically, the machine which has the highest value of the multiplication or division of the gene for machine selection and the value calculated using a machine selection rule is selected as the machine to process the next operation[3][4].

## 4.2 Job selection rules

From our previous research [3], the best priority rule for job selection is (SL/RPN)+SPT rule [5] as follows:

$$pri_{ij} = \frac{1}{p_{ijk}} \left( \max \left[ \frac{d_i - t - rpt_i}{rpn_i}, 0 \right] + 1 \right)^{-1} \quad (2)$$

The value of $rpt_i$ represents the total processing time of remaining operations. If an operation has alternative machines, the mean processing time is used. The value of $rpn_i$ represents the number of remaining operations. When a machine became idle and there are multiple waiting jobs to be processed at time t, the job with the highest value of $pri_{ij}$ is selected as the next job. This paper used this rule for job selection.

## 4.3 Machine selection rules

Also from the previous research [3], the best machine selection rule is (WINQ+RPT+PT)×PT rule [6]. This rule is the combination of WINQ, RPT and PT. These rules select the next machine as follows:
*   **PT**: The rule selects the machine which has the shortest processing time to process the next operation of the job.

*   **NINQ**: The rule selects the machine which has the smallest number of waiting jobs.

*   **WINQ**: The rule selects the machine which has the smallest summation of the processing times of waiting jobs.

*   **WINQ+RPT+PT**: The rule selects the machine which has the smallest summation of (1) the processing times of waiting jobs, (2) the remaining processing time currently being processed on the machine and (3) the processing time of the next operation when the operation is processed on the machine.

*   **(WINQ+RPT+PT)×PT**: The rule selects the machine which has the smallest value of {((1)+(2)+(3))×(3)}.

The rules described above are not using due-date related information. Because the objective of scheduling is related to due-dates, machine selection using due-date related information seems to be effective. In this paper we examine new machine selection rules using due-date related information as follows.

*   **MAX MIN SLACK**: The rule calculates slack value (= due-date - current time - sum of remaining processing time) for each waiting job in the input buffer of machine. Then the minimum slack value is selected for each machine. Finally, the machine which has the largest value of the minimum slack value is selected as the machine to process the next operation. The objective of this rule is to select the machine which has larger slack in terms of minimum value.

*   **MAX TOTAL SLACK**: The rule calculates the sum of slack values for all the waiting jobs in the input buffer of machine. Then the machine which has the largest value of the sum of slack values is selected as the machine to process the next operation. The objective of this rule is to select the machine which has larger slack in terms of total value.

*   **MIN MAX (SL/RPN)+SPT**: The rule calculates the value of equation (2) for each waiting job in the input buffer of machine. Then the maximum value of it is selected for each machine. Finally, the machine which has the smallest value of the maximum value is selected as the machine to process the next operation. The smaller value of equation (2) corresponds to larger slack value. Therefore, the machine with smaller value of the maximum value of equation (2) is selected.

*   **MIN TOTAL (SL/RPN)+SPT**: This rule calculates the sum of the values of equation (2) for all the waiting job in the input buffer of machine. Then the machine which has the smallest value of the sum of the values is selected as the machine to process the next operation.

*   **MIN MAX CR+SPT**: This rule uses CR+SPT rule [8] instead of (SL/RPN)+SPT in **MIN MAX (SL/RPN)+SPT**.

*   **MIN TOTAL CR+SPT**: This rule uses CR+SPT rule [8] instead of (SL/RPN)+SPT in **MIN TOTAL (SL/RPN)+SPT**.

*   **MIN MAX ATC**: This rule uses ATC rule [9] instead of (SL/RPN)+SPT in **MIN MAX (SL/RPN)+SPT**.

*   **MIN TOTAL ATC**: This rule uses ATC rule [9] instead of (SL/RPN)+SPT in **MIN TOTAL (SL/RPN)+SPT**.
*   **MAX MIN EDD:** This rule selects the earliest due-date in the input buffer of machine. Then the machine with the maximum value of it is selected as the next machine to process the next operation.

*   **MAX TOTAL EDD:** This rule calculates the sum of the due-date for all the waiting job in the input buffer of machine. Then the machine which has the largest value of it is selected as the machine to process the next operation.

# 5 Numerical Experiments

## 5.1 Numerical conditions

Numerical experiments are carried out to examine the effectiveness of the method in this paper. The number of job is 100. There are eight work centers ($R=8$) in the shop floor. Each work center has two machines ($M_r=2$). Any operation assigned to work center can be processed on both machines in the work center. The number of operations $n_i$ for each job is randomly determined between 4 and 8. The order of work centers to process each operation of a job is determined randomly. It is assumed that one of the machines in a work center can process the operations faster than the other machine. The processing time of an operation on the most efficient machine is determined by the uniform distribution between 5 and 100. The processing time on the other machine in the same work center is determined by multiplying a speed factor by the processing time on the most efficient machine. The speed factor is randomly determined by the uniform distribution between 1 and 2. The due-dates of jobs are determined based on TWK method [10]. The problems with two different levels of due-date tightness are generated. When the due-dates of jobs are loose, the number of tardy jobs is set to about 10%-15% by tuning the due-date factor in TWK method. When the due-dates of jobs are tight, the number of tardy jobs is set to about 25%-30%. The thirty problems are randomly generated. The scheduling performance is evaluated by the mean value of equation (1) for the thirty problems and the standard deviation from the best rules. For all the conditions, $(SL/RPN)+SPT$ rule is used for the job selection rule.

## 5.2 Experimental results

Table 1 and Table 2 show the experimental results when using heuristic rules alone. These are the results obtained not using the genetic algorithm. For both due-date tightness levels, $(WINQ+RPT+PT) \times PT$ rule for machine selection performed best. The best rule using due-date related information was MAX MIN SLACK.

Table 3 and Table 4 show the experimental results when using the genetic algorithm incorporating heuristic rules. MAX MIN SLACK rule is used as a machine selection rule which includes due-date related information. When incorporating MAX MIN SLACK rule, the minimum slack value can be negative. Therefore, when the value of minimum slack is $s$, the value $s^+ = \exp(s)$ is calculated and the maximum value of the multiplication of $s^+$ and the value of gene is used for machine selection in the genetic algorithm. The results in Table 3 and Table 4 indicate that $(WINQ+RPT+PT) \times PT$ rule performed best for incorporation for both due-date tightness levels.
<table><caption>**Table 1.** Mean tardiness using heuristic rules alone in the loose due-date condition</caption><thead><tr><td>Machine selection rules</td><td>Mean tardiness</td><td>S.D. from the best</td></tr></thead><tbody><tr><td>PT</td><td>755.8</td><td>102.5</td></tr><tr><td>NINQ</td><td>56.9</td><td>16.5</td></tr><tr><td>WINQ</td><td>59.7</td><td>18.4</td></tr><tr><td>WINQ+RPT+PT</td><td>34.9</td><td>11.8</td></tr><tr><td>(WINQ+RPT+PT)×PT</td><td>24.0</td><td>0.0</td></tr><tr><td>MAX MIN SLACK</td><td>60.3</td><td>19.9</td></tr><tr><td>MAX TOTAL SLACK</td><td>70.6</td><td>23.2</td></tr><tr><td>MIN MAX (SL/RPN)+SPT</td><td>68.1</td><td>21.9</td></tr><tr><td>MIN TOTAL (SL/RPN)+SPT</td><td>66.0</td><td>20.2</td></tr><tr><td>MIN MAX CR+SPT</td><td>85.8</td><td>27.8</td></tr><tr><td>MIN TOTAL CR+SPT</td><td>72.7</td><td>21.9</td></tr><tr><td>MIN MAX ATC</td><td>73.2</td><td>24.2</td></tr><tr><td>MIN TOTAL ATC</td><td>66.1</td><td>19.8</td></tr><tr><td>MAX MIN EDD</td><td>61.7</td><td>18.6</td></tr><tr><td>MAX TOTAL EDD</td><td>82.0</td><td>29.6</td></tr></tbody></table>

# 6 Conclusion

In this paper, a genetic algorithm incorporating heuristic rules is applied for job shop scheduling with alternative machines. There are two decision situations in this scheduling: job sequencing and machine selection. (SL/RPN)+SPT rule is used for job sequencing. Various machine selection rules are examined. Some rules such as WINQ, NINQ, (WINQ+RPT+PT)×PT are the ones which do not include due-date related information. Because the objective function for scheduling in this paper is mean tardiness, due-date related information seems to be important also for machine selection rules. However, the experimental results show that the best machine selection rule is (WINQ+RPT+PT)×PT rule both when using heuristic rules alone and when applying the genetic algorithm incorporating the heuristic rules. (WINQ+RPT+PT)×PT rule works for load balancing. Numerical results suggest that it is not necessary to include due-date related information in machine selection if the due-date related information is considered in job selection and load balancing is considered in machine selection appropriately.
<table><caption>**Table 2.** Mean tardiness using heuristic rules alone in the tight due-date condition</caption><thead><tr><td>Machine selection rules</td><td>Mean tardiness</td><td>S.D. from the best</td></tr></thead><tbody><tr><td>PT</td><td>837.6</td><td>92.2</td></tr><tr><td>NINQ</td><td>97.9</td><td>17.1</td></tr><tr><td>WINQ</td><td>99.6</td><td>17.6</td></tr><tr><td>WINQ+RPT+PT</td><td>65.5</td><td>9.1</td></tr><tr><td>(WINQ+RPT+PT)×PT</td><td>45.2</td><td>0.0</td></tr><tr><td>MAX MIN SLACK</td><td>96.4</td><td>19.4</td></tr><tr><td>MAX TOTAL SLACK</td><td>103.2</td><td>18.6</td></tr><tr><td>MIN MAX (SL/RPN)+SPT</td><td>107.8</td><td>25.1</td></tr><tr><td>MIN TOTAL (SL/RPN)+SPT</td><td>101.2</td><td>21.5</td></tr><tr><td>MIN MAX CR+SPT</td><td>126.1</td><td>23.4</td></tr><tr><td>MIN TOTAL CR+SPT</td><td>110.2</td><td>22.1</td></tr><tr><td>MIN MAX ATC</td><td>114.3</td><td>25.3</td></tr><tr><td>MIN TOTAL ATC</td><td>108.5</td><td>22.5</td></tr><tr><td>MAX MIN EDD</td><td>99.4</td><td>19.4</td></tr><tr><td>MAX TOTAL EDD</td><td>123.2</td><td>28.5</td></tr></tbody></table>

**References**

1. Nasr, N., Elsayed, E., A. : Job shop scheduling with alternative machines, International Journal of Production Research, Vol.28, No.9, pp.1595-1609 (1990)

2. Moon, I., Lee, S. and Bae, H. : Genetic algorithm for job shop scheduling problems with alternative routing, International Journal of Production Research, Vol.46, No.10, pp.2695-2705 (2008)

3. Kaweegitbundit, P. and Eguchi, T. : Job shop scheduling with alternative machines using genetic algorithm incorporating heuristic rules. In: Mechanical Engineering Congress, 2014 Japan[MECJ-14], No.14-1, S1420140, The Japan Society of Mechanical Engineers, Tokyo (2014)

4. Eguchi, T., Kaweegitbundit, P., Hoshino, N., Daido, T., Murayama T. : Job shop scheduling with alternative machines—Experimental evaluation of the scheduling method using a genetic algorithm incorporating heuristic rules—. In: Manufacturing Systems Division Conference 2015, No.15-8, pp.95-96, The Japan Society of Mechanical Engineers, Tokyo (2015)
<table><caption>**Table 3.** Mean tardiness using the genetic algorithm incorporating heuristic rules in the loose due-date condition</caption><thead><tr><td>Machine selection rules</td><td>Mean tardiness</td><td>S.D. from the best</td></tr></thead><tbody><tr><td>GA+ PT</td><td>22.4</td><td>8.5</td></tr><tr><td>GA+ NINQ</td><td>16.9</td><td>5.3</td></tr><tr><td>GA+ WINQ</td><td>17.4</td><td>5.4</td></tr><tr><td>GA+ WINQ+RPT+PT</td><td>12.0</td><td>2.4</td></tr><tr><td>GA+ (WINQ+RPT+PT)×PT</td><td>9.9</td><td>0.0</td></tr><tr><td>GA+ MAX MIN SLACK</td><td>20.4</td><td>8.0</td></tr></tbody></table>

<table><caption>**Table 4.** Mean tardiness using the genetic algorithm incorporating heuristic rules in the tight due-date condition</caption><thead><tr><td>Machine selection rules</td><td>Mean tardiness</td><td>S.D. from the best</td></tr></thead><tbody><tr><td>GA+ PT</td><td>46.4</td><td>10.2</td></tr><tr><td>GA+ NINQ</td><td>38.6</td><td>5.4</td></tr><tr><td>GA+ WINQ</td><td>39.0</td><td>5.2</td></tr><tr><td>GA+ WINQ+RPT+PT</td><td>31.1</td><td>3.0</td></tr><tr><td>GA+ (WINQ+RPT+PT)×PT</td><td>26.7</td><td>0.0</td></tr><tr><td>GA+ MAX MIN SLACK</td><td>45.5</td><td>9.8</td></tr></tbody></table>

5. Yoda, M., Eguchi, T., Murayama, T. : Job shop scheduling for meeting due dates and minimizing overtime using genetic algorithm incorporating new priority rules, Journal of Advanced Mechanical Design, Systems, and Manufacturing, Vol.8, No.5, Paper No.14-00076 (2014)

6. Eguchi, T., Oba, F., Toyooka, S., Sato, Y. : A Machine Selection Rule for Dynamic Job Shop having Alternative Machines with Different Processing Times, Journal of the Japan Society for Precision Engineering, Vol.72, No.4, pp.459-464 (2006)

7. Eguchi, T., Oba, F., and Kozaki, S. : Dynamic scheduling using the mixture of a genetic algorithm and a priority Rule, Transactions of the Japan Society of Mechanical Engineers Series C, Vol.71, No.703, pp.1047-1053 (2005) (in Japanese)

8. Anderson, E.J. and Nyirenda, J.C. : Two new rules to minimize tardiness in a job shop, International Journal of Production Research, Vol.28, No.12, pp.2277-2292 (1990)

9. Vepsalainen, A.P.J., and Morton, T.E. : Priority rules for job shop with weighted tardiness costs, Management science, Vol.33, No.8, pp.1035-1047 (1987)

10. Conway, R.W. : Priority dispatching and job lateness in a job shop, The Journal of Industrial Engineering, Vol.16, No.4, pp.228-237 (1965)