ABSTRACT

The purpose of this research is to present a straightforward and relatively efficient method for solving scheduling problems. A new heuristic algorithm, with the objective of minimizing the makespan, is developed and presented in this paper for job shop scheduling problems (JSP). This method determines jobs’ orders for each machine. The assessment is based on the combination of dispatching rules e.g. the “Shortest Processing Time” of each operation, the “Earliest Due Date” of each job, the “Least Tardiness” of the operations in each sequence and the “First come First Serve” idea. Also, unlike most of the heuristic algorithms, due date for each job, prescribed by the user, is considered in finding the optimum schedule. A multitude of JSP problems with different features are scheduled based on this proposed algorithm. The models are also solved with Shifting Bottleneck algorithm, known as one of the most common and reliable heuristic methods. The result of comparison between the outcomes shows that when the number of jobs are less than or equal to the number of machines, the proposed algorithm concludes smaller, and better, makespan in a significantly lower computational time, which shows the superiority of the suggested algorithm. In addition, for a category when the number of jobs are greater than the number of machines, the suggested algorithm generates more efficient results when the ratio of the number of jobs to the number of machines is less than 2.1. However, in this category for the mentioned ratio to be higher than 2.1, the smaller makespan could be generated by either of the methods, and the results do not follow any particular trend, hence, no general conclusions can be made for this case.

Keywords:

Heuristic Algorithm, Job Shop Scheduling, Shifting Bottleneck, Makespan

1. Introduction

Job shop scheduling (JSP) has been one of the most critical subjects in optimization and applied mathematics in the past few decades. Its vast applicability in the industry and all economic domains, and on the other hand its complexity, specifically for large-scale problems, make this topic very critical [1] [2] . JSP is an NP-hard problem due to its computational complicacy [3] [4] . Based on the scheduling literature, a relatively small problem consists of 10 jobs and 10 machines, proposed by Muth and Thompson [5] , remained unsolved for more than a quarter of a century. Also, the fact that a scheduling problem included 15 jobs and 15 machines is considered unsolvable with the exact method nowadays, clearly shows the sophistication of this kind of problems [6] [7] .

In job shop scheduling problems “n” jobs are needed to be processed in “m” machines. Each job includes some operations, each of which are required to be done by a particular machine. Each machine only can process one job at a time and cannot be interrupted [8] . The order of jobs in each machine is calculated by minimizing a specific character. In this paper, the completion time of all jobs, which is called makespan, is the objective [9] .

Lots of algorithms and procedures have been proposed for efficiently scheduling JSP, which are divided into three major groups: 1) the exact algorithms; such as the one proposed by Giffler and Thompson (1960), and branch and bound by Lageweg, Lenstra and Rinnooy Kan (1977) [7] . This group results are surely optimum, but they are too time-consuming to reach, 2) heuristic procedures; such as Palmer, Johnson and Shifting Bottleneck algorithms. They are not always derived optimum answer; some gives answers close to optimum. Comparing to two other groups, the computational time of algorithms in this category is relatively small, 3) meta-heuristic Algorithms; such as genetic algorithm, and SA and TS algorithms by Fattahi, Mehrabad and Jolai [10] . This group does not guaranty the optimal answer, but present better results comparing to the second group.

A new heuristic algorithm is presented in this paper for optimally scheduling JSP. This method is the result of combining different dispatching rules, so, its implementation is justly straightforward. It is also worth to mention that tardiness is the difference between the completion time of each job (or operation) and the job’s related due date (or relative due date); in other words, the time that a job takes to be completed after its due date arrives is called tardiness.

Due to the complexity of developing a reliable and efficient algorithm, some heuristic algorithms just consider operations’ processing times, ignoring the jobs’ due dates and others are designed based on the due dates and ignored the processing time. However, the new algorithm presented in this paper takes both factors into account.

Furthermore, the new method can schedule both job shop and flow shop problems. In flow shop problems, all jobs should be operated in all machines in the same order. However, job shop scheduling is more general, and the sequence of machines in each job may not follow a specific order [11] . So, unlike algorithms like Johnson and NEH, which are only applicable and useful in flow shop problems, the proposed algorithm is capable of handling the job shop schedule as well. The new algorithm detail is described in the following section.

Among all existing heuristic algorithms, Shifting Bottleneck algorithm is one of the most well-known and reliable ones. Therefore, to evaluate the reliability of the new algorithm, its results have been compared to the Shifting Bottleneck outcomes. Scheduling models for comparison of two algorithms are JSP problems. The comparison of outcomes is reported in the Results section. Finally, based on the observed results, conclusions will be made.

2. Materials and Methods

2.1. Proposed Algorithm Description

The proposed algorithm has been developed based on some primary dispatching rules including “earliest due date” of each job, “shortest processing time” of each operation, “least tardiness” of operations in each sequence and “first come first serve” idea. The theory behind using these simple rules is to create a heuristic method with a straightforward procedure to apply to JSP problems, concluding to acceptable results. The efficiency of the results comparing to other heuristic algorithms, is also contemplated. Besides, the proposed method is designed in such a way that the due dates’ values required to be specified by the user. This advantage can equip users to affect their tendency in using specific due dates in the scheduling problems.

Moreover, the sequence of operations and their related processing times for each job are needed to be imported. Besides, the user is required to clarify the machine used for each operation. The procedures’ details of the new algorithm are being described on a small example to explain the steps thoroughly.

Table 1 shows a JSP example, consisting of 3 jobs and 3 machines. The processing times and due dates are also specified. Each job is defined in each row of the table. Each job consists of some operations, required to be done by a particular machine, which each of the operations has a deterministic processing time specified in the table. For instance, Job 1 has three operations; first operation processing time is 7 minutes (instead of minutes any unit of time can be used), and it needs to be done by machine 1 (M1).

1) Step 1: The minimum value of all the provided due dates is selected and subtracted from the rest of the due dates; the result values are called relative due

dates. There are two reasons for doing so: 1^st reason is that this way it is not necessary to deal with values of due dates, which might be significantly large. And the second reason is that urgency of the jobs can be compared more clearly. The results of the subtraction for the mentioned example in Table 1, is elaborated in Table 2.

2) Step 2: The new algorithm is task wise, which means the priority is the first to be operated task in each job, which is derived from the primary rule “first come first serve”. In the mentioned example the priority is the column by the title of “1st Operation” (second column of the table). These are tasks, which are needed to be completed in their related jobs, for jobs to be able to go to the next stage. Based on the explained idea, the first tasks are considered first. If there is no ready time for an operation (best situation), its completion time will be equal to their related processing time. Therefore, for each operation, the tardiness will be equivalent to the operation’s relative due date, subtracted by the related completion time or the operation processing time. The procedure is presented in Table 3. The order of implementation will be based on the least tardiness such that, the operation with the lowest tardiness takes place first, and the operation with the most massive tardiness will take place at last. If there is a tie-breaker, the algorithm chooses the operation based on the job orders; for example in the mentioned case, between the 1st operation of job 1 and 1st operation of job 3, the priority for the algorithm is job 1.

For clarification of the proposed method, execution of each step is demonstrated in a diagram, similar to Gantt chart. Gantt chart is a bar chart used to demonstrate a project schedule, which in job shop scheduling problems it usually illustrates the order of jobs in each machine. However, in the diagrams used in this paper, called modified Gantt chart, the charts show the sequence of machines in each job (with consideration of their order and waiting time). Figure 1

shows the implementation of step 2.

3) Step 3: The procedure in this step is the same as step two, just the considered completion times are different. They are equal to the processing time of each job from the start of the job until the end of the current operation. For instance, the completion time of job 1 after the end of task 2 is equal to the summation of 7 and 8 (7 + 8 = 15). Table 4 displays the detail of this step on the mentioned example. Also, the implementation of this step on modified Gantt chart is shown in Figure 2.

4) Step 4: This step is also similar to the two previous ones, by considering the completion time of each job up to the end of the current operation. The procedure detail and implementation on modified Gantt chart for this stage are described in Table 5 and Figure 3 consequently. Based on the modified Gantt chart it is clear that the makespan is 33.

It is also worth to mention that the completion time of all jobs (makespan) is equal to the completion time of all machines. As it is mentioned earlier the implementation of the operations should be in a way to avoid confliction between the machines; in other words, the ready time for each operation and the processing time of the machine before starting the current operation are needed to be considered. So, for the mentioned instance, the sequence of jobs in each machine is derived as follow:

a) M1: Job 1 − Job 2 − Job 3

b) M2: Job 3 − Job 2 − Job 1

c) M3: Job 2 − Job 1 − Job 3

With the same procedure implemented to the mentioned example, any number of jobs and machines can be scheduled by the proposed algorithm. The algorithm is also presented in the form of the flowchart in Figure 4.

For a new algorithm to be evaluated, it is necessary to be compared with a well-known and reliable existing algorithm in various models. One of the most popular and acceptable heuristic algorithms, which is known to be superior among heuristic algorithms for JSP, is Shifting Bottleneck algorithm proposed by Adams, Egon and Zawack [8] .

2.2. Shifting Bottleneck Algorithm

This algorithm does not guaranty the optimum answer, but its results are so

promising, especially on benchmark problem sets from the literature, such that lots of researchers like, Dauzere-Peres and Lasserre (1993) and Schutten (1995), consider it as a fundamental algorithm for their work. However, the efficiency of this algorithm may be reduced by increament of the ratio of number of machines per number of jobs [12] .

Shifting bottleneck algorithm approach is machine wise. It is solved a one- machine scheduling problem at a time for all not sequenced machines. Then based on the rank of scheduled machines, it sets the job sequence for the highest rank machine and reorders the job sequence for others. This method is chosen for comparison with the new proposed algorithm in this paper.

3. Results

The proposed and Shifting Bottleneck algorithms have been coded in MATLAB

software and their results for different problems have been compared. The models considered for comparison could be divided to three major groups; those with equal number of jobs and machines, the ones with greater number of jobs than machines and visa versa. For each category, problems with different sizes, small, medium and large, have been examined. Each problem is solved 27 times with 27 different sets of randomly generated due dates. The results for all the 27 sets, derived by the proposed method and Shifting Bottleneck algorithm, are compared. The comparison results are presented in three different tables. Table 6 is allocated to the models with the same number of jobs and machines. Table 7 is associated with the models with the higher number of machines. Finally, the models with the higher number of jobs are presented in Table 8.

Since the proposed algorithm gets advantage of the assigned due dates in the calculation of the makespan, changing them may result in varying the outcomes consequently. However, the Shifting Bottleneck algorithm does not consider the due dates provided by users, so its results will remain unchanged. In each model 27 different cases, with a set of randomly generated due dates, have been scrutinized. For each model, the results derived by the new algorithm in all the cases have been compared to the ones derived from the Shifting Bottleneck algorithm,

but to save the space, for each model, just the average of the results of 27 states is presented here. The percentage of the number of the times that the new algorithm produces lower makespan is also reported here. Therefore, for each group of problems two algorithms have been compared 270 times or more. The observation from the compared models is noted in this section. It is worth to mention that all the considered processing times are chosen randomly.

As it is shown in Table 6, the new algorithm produces lower makespan in almost all iterations. Moreover, it is observed that by increasing the size of the problem in this category (number of jobs and machines) the difference, between the computational time generated by the two algorithms becomes significant. Growing the problem size is also concluded to the variation of makespans, produced by two methods for an identical problem, to be increased considerably.

When the number of machines is higher than the number of jobs in all cases the derived makesspan by the proposed method is lower than the identical ones derived from the Shifting Bottleneck algorithm. The difference between the computational time is also increased by the increment of the size of the problem. The details are presented in Table 7.

Eventually, for the category, in which the number of jobs is higher than the number of machines, there is no consistency observed in the results. Extensive testing problems have been scheduled in this case, which for the sake of saving the space only, 350 selected models have been presented in this paper. It is noted that when the ratio of the number of jobs to the number of machines, is less than or equal to 2.1, in almost all circumstances, the proposed algorithm produces lower makespan, in a smaller computational time. However, when the mentioned ratio is higher than 2.2, the observed results do not have solidarity, which means in some situations the proposed algorithm, and in some other cases Shifting Bottleneck algorithm, generates lower makespan.

4. Conclusions

A new algorithm for scheduling job shop problems has been proposed in this article. This algorithm is based on the combination of some primary dispatching rules like the “Shortest Processing Time” of each operation, the “Earliest Due Date” of each job, the “Least Tardiness” of the operations in each sequence and the “First come First Serve” idea. Straightforward procedures and ease of implementation are two of the most significant advantages of the proposed method. The flowchart and the execution steps have been described in previous sections in detail.

For numerical evaluation and verification of the suggested method, its produced results have been compared to the outcomes derived by the Shifting Bottleneck algorithm for enormous problems. Results comparison is presented in this paper for more than 30 models with almost 900 different iterations (using random due dates).

Based on the compared models, it is observed that when the number of jobs is less than or equal to the number of machines, the proposed algorithm produces lower makespan in a significantly smaller computational time, which shows the superiority of the proposed method. Also, the larger the size of the problem, the more the difference between the identical makespans generated by two methods. Besides, in the mentioned categories, in the models with a larger size for an identical problem, the computational time by the new method is remarkably less than the computational time by the Shifting Bottleneck algorithm.

It is also observed that when the ratio of the number of jobs to the number of machines, is less than 2.1, the proposed algorithm produces lower makespan in a smaller computational time. But, when the mentioned ratio becomes greater than 2.1, the smaller makespan could be generated by either of the methods, and the results do not follow any particular trend, hence, no general conclusions can be made for this case.

It is also perceived that for all the tested cases, the computational period of the proposed method is lower than the computational time of the Shifting Bottleneck algorithm.

Acknowledgements

Authors would like to thank Old Dominion University for providing resources to facilitate this project.

Cite this paper

Ehsaei, M. and Nguyen, D.T. (2017) A New Job Shop Heuristic Algorithm for Machine Scheduling Problems. Journal of Applied Mathematics and Physics, 5, 2172-2182. https://doi.org/10.4236/jamp.2017.511177

References