摘要
研究了三台机器调整时间可分离的FlowShop调度问题 ,目标函数为极小化最大完工时间·证明了最优调度可能不是排列调度 ,但是工件在前两台机器上具有相同加工顺序的调度中至少存在最优调度·在排列调度范围内 ,对于工件在第二台机器上的调整时间与加工时间之和的最大值不超过工件在第一台或第三台机器上的调整时间与加工时间之和的最小值的情况 ,给出了求解最优调度分派规则 。
The three machine flow shop scheduling problem with set up time separated was studied. The objective function is to minimize makespan. The optimal schedule was proved to be not permutation schedule. But there is at lest an optimal schedule in the schedules that jobs have same order in first two machines. For permutation schedule, a dispatching rule was given for the case that the maximum of sum of set-up time and processing time on the second machine is no larger than the minimum of sum of set up time and processing time on the first machine or the third machine. Based on the dispatching rule,an optimal polynomial algorithm was presented.
出处
《东北大学学报（自然科学版）》
EI
CAS
CSCD
北大核心
2002年第3期300-302,共3页
Journal of Northeastern University(Natural Science)
基金
辽宁省科委自然科学基金资助项目 (9910 70 0 1)
辽宁省教育厅高等学校科学研究项目 (2 0 2 62 2 5 0 9112 15 5 8)
关键词
调度
流水作业
调整时间
最优算法
scheduling
flow Shop
set up time
NP hard
optimal algorithm
