A FPTAS Based Scheduling of a New Hub Reentrant Shop
We study a variant of the reentrant shop problem of minimizing makespan in one hub machine At, and two machine centers M2 and M3 (each center consists of some identical machines). In the problem, each job has five operations, where the first, the third and the fifth operation must be performed on hub machine Mt, the second operation can be performed on any one machine in M2 and the forth operation can be performed on any one machine in My We show the problem is strongly NP-hard, which motivates us to design approximation algorithms. We give a fully polynomial time approximation scheme (FPTAS) for the job-machine assignment decision in M2 and M3. Based on the FPTAS, we then provide a mixed integer linear programming (MILP) to schedule job operations optimally.
scheduling hub reentrant job shop hybrid flew shop makespan approximation algorithm
Xie Xie Yanping Li
Key Laboratory of Manufacturing Industrial and Integrated Automation, Shenyang University, Shenyang Liaoning, 110044, China
国际会议
昆明、丽江
英文
357-361
2011-04-15（万方平台首次上网日期，不代表论文的发表时间）