JAMP  Vol.5 No.11 , November 2017
A New Job Shop Heuristic Algorithm for Machine Scheduling Problems
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.
Cite this paper: Ehsaei, M. and Nguyen, D. (2017) A New Job Shop Heuristic Algorithm for Machine Scheduling Problems. Journal of Applied Mathematics and Physics, 5, 2172-2182. doi: 10.4236/jamp.2017.511177.

[1]   Bagheri, A. and Zandieh, M. (2003) An Artificial Immune Algorithm for the Flexible Job-Shop Scheduling Problem. Future Generation Computer Systems, 26, 13-20.

[2]   Nguyen, S., Zhang, M., Johnston, M. and Tan, K.C. (2012) Evolving Reusable Operation-Based Due-Date Assignment Models for Job Shop Scheduling with Genetic Programming. European Conference on Genetic Programming, Malaga, 11-13 April 2012, 121-133.

[3]   Zhang, R. and Wu, C. (2011) An Artificial Bee Colony Algorithm for the Job Shop Scheduling Problem with Random Processing Times. Entropy, 13, 1708-1729.

[4]   Brucker, P., Jurisch, B. and Sievers, B. (1994) A Branch and Bound Algorithm for the Job-Shop Scheduling Problem. Discrete Applied Mathematics, 49, 107-127.

[5]   Muth, J.F. and Thompson, G.L. (1963) Industrial Scheduling. Prentice-Hall, Englewood Cliffs, N.J.

[6]   Zhang, C.Y., Li, P., Rao, Y. and Guan, Z. (2008) A Very Fast TS/SA Algorithm for the Job Shop Scheduling Problem. Computers & Operations Research, 35, 282-294.

[7]   Lageweg, B.J., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1978) A General Bounding Scheme for the Permutation Flow-Shop Problem. OPNS RES, 26, 53-67.

[8]   Adams, J., Egon, B. and Zawack, D. (1988) The Shifting Bottleneck Procedure for Job Shop Scheduling. Management Science, 34, 391-401.

[9]   Bhosale, P.P. and Kalshetty, Y.R. (2016) Genetic Algorithm for Job Shop Scheduling. International Journal of Innovations in Engineering and Technology (IJIET), 7, 357-361.

[10]   Fattahi, P., Mehrabad, M.S. and Jolai, F. (2007) Mathematical Modeling and Heuristic Approaches to Flexible Job Shop Scheduling Problems. Journal of intelligent manufacturing, 18, 331-342.

[11]   Abbas, M., Abbas, A. and Khan, W.A. (2016) Scheduling Job Shop—A Case Study. IOP Conference Series: Material Science and Engineering, 146, 021052.

[12]   Demirkol, E., Mehta, S. and Uzsoy, R. (1997) A Computational Study of Shifting Bottleneck Procedures for Shop Scheduling Problems. Journal of Heuristic, 3, 111-137.