摘要
有N个成组工件将在M台并行一致的机器上加工 ,当一个工件接在不同组的工件之后时需要装设 ,而接在同组工件之后时不需要重新装设 ,目标函数是使总的通过时间最短。这是一个NP难题 ,最优解很难找到。笔者在文中提出了一个启发式算法 ,为了验证该算法的结果 ,又提出了一个求解最优解下界的线性规划模型 ,并用分枝定界法求解出下界解。在中小规模问题条件下 ,将下界解、启发式的解及最优解进行比较 ,证明了下界解的有效性。然后 ,在中等规模水平上 ,将启发式算法的结果与下界解进行了比较 ,最终证明该启发式算法具有解决大规模实际问题的潜力。
This paper presents a job scheduling model of M identical machines in parallel. The model assumes that a set-up time is incurred when a machine changes from processing one type of parts to a different type of parts. And the scheduling objective is to minimize the sum of total flow time. We establish a heuristic and a tight lower bound (LB) on the optimal total flow time. The solution is analyzed by computational study. The comparisons of LB with heuristic and optimal solutions of small instances show that the solution quality of our heuristic is acceptable, and the heuristic has potential to solve larger practical problems.
基金
国家自然科学基金 (6 96 840 0 5 )
国家 86 3/CIMS主题资助项目 (86 3 -5 11-0 844-0 11)
西安交通大学机械制造系统工程国家重点
关键词
成组工件调度
并行多机调度
最优化
启发式算法
NP问题
group technology
grouped jobs scheduling
parallel machine scheduling
optimization
heuristic algorithm
branch
bound
