TITLE:
A New Job Shop Heuristic Algorithm for Machine Scheduling Problems
AUTHORS:
Maryam Ehsaei, Duc T. Nguyen
KEYWORDS:
Heuristic Algorithm, Job Shop Scheduling, Shifting Bottleneck, Makespan
JOURNAL NAME:
Journal of Applied Mathematics and Physics,
Vol.5 No.11,
November
13,
2017
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.