Genetic algorithm for scheduling reentrant jobs on parallel machines with a remote server

Abstract

This paper considers a reentrant scheduling problem on parallel primary machines with a remote server machine, which is required to carry out the setup operation. In this problem, each job has three operations. The first and last operations are performed by the same primary machine, implying the reentrance, and the second operation is processed on the single server machine. The order of jobs is predetermined in our context. The challenge is to assign jobs to the primary machines to minimize the makespan. We develop a genetic algorithm (GA) to solve this problem. Based on a simple strategy of assigning jobs in batches on the parallel primary machines, the standardized random key vector representation is employed to split the jobs into batches. Comparisons among the proposed algorithm, the branch and bound (BB) algorithm and the heuristic algorithm, coordinated scheduling (CS), which is only one heuristic algorithm to solve this problem in the literature, are made on the benchmark data. The computational experiments show that the proposed genetic algorithm outperforms the heuristic CS and the maximum relative improvement rate in the makespan is 1.66%.

Keywords

scheduling / genetic algorithm / reentry / parallel machine / remote server

References

[1] Abdekhodaee A H, Wirth A. Scheduling parallel machines with a single server: Some solvable cases and heuristics[J]. Computers and Operations Research, 2002, 29(3): 295 315

[2] Abdekhodaee A H, Wirth A, Gan H S. Scheduling two parallel machines with a single server: The general case[J]. Computers and Operations Research, 2006, 33(4): 994 1009

[3] Allahverdi A, Ng C T, Cheng T C E, et al. A survey of scheduling problems with setup times or costs[J]. European Journal of Operational Research, 2008, 187(3): 985 1032

[4] Zhang L, Wirth A. On-line scheduling of two parallel machines with a single server[J]. Computers and Operations Research, 2009, 36(5): 1529 1553

[5] Huang S M, Cai LN, Zhang X Y. Parallel dedicated machine scheduling problem with sequence dependent setups and a single server[J]. Computers and Industrial Engineering, 2010, 58(1): 165-174.

[6] Guo S, Kang Liying. Online scheduling of malleable parallel jobs with setup times on two identical machines[J]. European Journal of Operational Research, 2010, 206(3): 555 561

[7] Gan H S, Wirth A, Abdekhodaee A. A branch-and-price algorithm for the general case of scheduling parallel machines with a single server[J]. Computers and Operations Research, 2012, 39(9): 2242 2247

[8] Turker A K, Sel C. Scheduling two parallel machines with sequence-dependent setups and a single server[J]. Gazi University Journal of Science, 2011, 24(1): 113-123.

[9] Kim M Y, Lee Y H. MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server[J]. Computers and Operations Research, 2012, 39(11): 2457 2468

[10] Wang G, Cheng T C E. An approximation algorithm for parallel machine scheduling with a common server[J]. Journal of the Operational Research Society, 2001, 52(2): 234-237.

[11] Wang M Y, Sethi S P, van de Velde S L. Minimizing makespan in a class of re-entrant shops[J]. Operations Research, 1997, 45(5): 702-712.

[12] Chakhlevitch H, Glass C A. Scheduling reentrant jobs on parallel machines with a remote server[J]. Computers and Operations Research, 2009, 36(9): 2580 2589

[13] Holland J H. Adaptation in Natural and Artificial Systems[M]. 1975, Ann Arbor: The University of Michigan Press.

[14] Davis L. Handbook of Genetic Glgorithms[M]. 1991, New York: Van Nostrand.

[15] Abdelmaguid T F. Representations in genetic algorithm for the job shop scheduling problem: A computational study[J]. Journal of Software Engineering and Applications, 2010, 3(12): 1155-1162.

[16] Benchmark Data [EB/OL]. http://people.brunel.ac.uk/~mastjjb/jeb/orlib/HybridReentrantShop01.html.