摘要
讨论了一类两机器流水作业的总延误问题,其中每个工件的操作由“调整”步、“加工”步及“移走”步组成,而工件的调整时间和移走时间均独立于加工时间,同一工件的“调整”步及“移走”步在2台机器上可重叠进行,但“加工”步不能重叠,并且第一台机器上没有空闲时间,工件一旦开始加工就不允许中断.给出了该问题的解中工件排列应满足的条件,并根据这些条件构建了几个近似算法.在构建分支定界算法时,利用问题目标函数的下界及近似算法的结果给出了剪支法则,由此说明所给近似算法对某些例子是很有效的.
In this paper, we discuss the total tardiness in two-machines flowshop problem with setup and removal time separated, where setup step and removal step of the same job is overlap on two machine, but the processing step can not be, and there is not idleness on the machine M1. We give the conditions satisfied by sequence in solution of total tardiness flowshop problem. From these conditions, we construct some approximation algorithms. In order to get the brance and bound method, we also give the lower bound. The computational results indicate that the above approximation algorithm is efficient.
出处
《宁夏大学学报（自然科学版）》
CAS
北大核心
2005年第3期211-215,共5页
Journal of Ningxia University(Natural Science Edition)
基金
江苏省高校自然科学基金资助项目(03KJB110012)
江苏省教育厅自然科学基金资助项目(01KJD110005)
关键词
流水作业
调整时间
移走时间
加工时间
总延误
近似算法
分支定界法
flowshop
setup time
removal time
process time
total tardiness
approximation algorithm
brance and bound method
