Multiple Job Shop-Scheduling using Hybrid Heuristic Algorithm

Authors: R.A.Mahdavinejad

Abstract:

In this paper, multi-processors job shop scheduling problems are solved by a heuristic algorithm based on the hybrid of priority dispatching rules according to an ant colony optimization algorithm. The objective function is to minimize the makespan, i.e. total completion time, in which a simultanous presence of various kinds of ferons is allowed. By using the suitable hybrid of priority dispatching rules, the process of finding the best solution will be improved. Ant colony optimization algorithm, not only promote the ability of this proposed algorithm, but also decreases the total working time because of decreasing in setup times and modifying the working production line. Thus, the similar work has the same production lines. Other advantage of this algorithm is that the similar machines (not the same) can be considered. So, these machines are able to process a job with different processing and setup times. According to this capability and from this algorithm evaluation point of view, a number of test problems are solved and the associated results are analyzed. The results show a significant decrease in throughput time. It also shows that, this algorithm is able to recognize the bottleneck machine and to schedule jobs in an efficient way.

Keywords: Job shops scheduling, Priority dispatching rules, Makespan, Hybrid heuristic algorithm.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1334790

References:

[1] P.Brucker, J.Hurink and F. Warner, “Improving local search heuristic for some scheduling problems part II," Discrete Applied Mathematics 72/1-2, 1997, 47-69.
[2] Blackstone, Philips and Hogg, "A state of the art survey of dispatching rules for manufacturing job-shop operations," International Journal of Production Research, Vol.20, 1982, pp.27-45.
[3] Biegel and Wink," Expert system can do job-shop scheduling: an exploration and a proposal," Computers and Industrial Engineering Vol.17/1-4, 1989, pp.347-352.
[4] Colorni, Dorigo, Maniezzo and Trubian,"Ant-system for job-shop scheduling," Belgian Journal of Operations Research, Statics and Computer Science,Vol. 34/1,2002, pp. 39-54.
[5] G.Shi," A genetic algorithm applied to a classic job-shop scheduling problem, "International Journal of Systems Science, Vol. 28/1, 1997, pp.25-32.
[6] P. Brucker,B.Jurisch,B.Sievers," A branch and bound algorithm for the job-shop scheduling problem," Discrete Applied Mathematics, Vol. 49,1994, pp. 109-127.
[7] E.Demirkol, S.Mehta, R.Uzsoy," A computational study of shifting bottleneck procedures for shop scheduling problems," Journal of Heuristic, Winter, Vol. 3/2, 2003, pp. 111-137.
[8] E.Nowicki , C.Smutnicki, "A fats taboo search algorithm for the jobshop problem," Management Science, Vol. 42/6, 1996, pp. 797-813.
[9] M.Kolonko," Some new results on simulated annealing applied to the job-shop scheduling problem," European Journal of Operational Research , Vol. 21,1998, pp. 112-121.
[10] A.S.Jain, S.Meeran," Job-shop scheduling using neural networks, "International Journal of production research , Vol. 36/5, 1998, pp. 1249-1272.
[11] E. Balas, "Machine scheduling via disjunctive graphs: An implicit enumeration algorithm," European Journal of Operational Research , Vol. 17,1969, pp.941-957.
[12] T.Yamada,R.Nakano, "Job-shop scheduling by simulated annealing combined with deterministic local search, "MIC-95 Metaheuristic International Conference, Hilton, Breckenridge, Colorado, USA ,1995, pp.344-349.
[13] B.Grabot,L.Geneste, "Dispatching rules in scheduling: A fuzzy approach, "International Journal of production Research,Vol. 32/4, 1994, pp. 903-915.
[14] T.Yamada,R.Nakano," Scheduling by genetic local search with multistep crossover, PPSN-IV" Fourth International Conference on parallel problem solving from nature, Berlin, Germany, 1996, pp. 22-26.
[15] G.N.Varela , M.C.Sinclair, "Ant colony optimization for virtual -wave length-path routing and wave length allocation," In CEC'99, Proceedings of the Congress on Evolutionary Computation, 1999, pp. 1809-1816.