Genetic Algorithm for Scheduling Reentrant Jobs on Parallel Machines with a Remote Server  

作　　者：王宏 李海娟 赵月 林丹 李建武 

机构地区：[1]School of Sciences,Tianjin University [2]Beijing Key Laboratory of Intelligent Information Technology, School of Computer Science and Technology,Beijing Institute of Technology

出　　处：《Transactions of Tianjin University》2013年第6期463-469,共7页天津大学学报（英文版）

基　　金：Supported by National Natural Science Foundation of China(No.61271374);Beijing Natural Science Foundation(No.4122068)

摘　　要：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%.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%.

关 键 词：scheduling genetic algorithm reentry parallel machine remote server 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP368.5[自动化与计算机技术—控制科学与工程]