| 有分离调整和移走时间的两机器流水作业总延误问题的近似算法 |
| |
| 引用本文： | 陈秀宏.有分离调整和移走时间的两机器流水作业总延误问题的近似算法[J].宁夏大学学报(自然科学版),2005,26(3):211-215. |
| |
| 作者姓名： | 陈秀宏 |
| |
| 作者单位： | 淮阴师范学院,数学系,江苏,淮安,223001 |
| |
| 基金项目： | 江苏省高校自然科学基金资助项目（03KJB110012）;江苏省教育厅自然科学基金资助项目（01KJD110005） |
| |
| 摘 要： | 讨论了一类两机器流水作业的总延误问题，其中每个工件的操作由“调整”步、“加工”步及“移走”步组成，而工件的调整时间和移走时间均独立于加工时间，同一工件的“调整”步及“移走”步在2台机器上可重叠进行，但“加工”步不能重叠，并且第一台机器上没有空闲时间，工件一旦开始加工就不允许中断．给出了该问题的解中工件排列应满足的条件，并根据这些条件构建了几个近似算法．在构建分支定界算法时，利用问题目标函数的下界及近似算法的结果给出了剪支法则，由此说明所给近似算法对某些例子是很有效的．
|
| 关 键 词： | 流水作业 调整时间 移走时间 加工时间 总延误 近似算法 分支定界法 |
| 文章编号： | 0253-2328（2005）03-0211-05 |
| 收稿时间： | 2004-08-30 |
| 修稿时间： | 2004年8月30日 |
Minimizing Total Tardiness in Two-Machines Flowshop with Setup, Processing and Removal Time Separated |
| |
| Chen Xiuhong.Minimizing Total Tardiness in Two-Machines Flowshop with Setup, Processing and Removal Time Separated[J].Journal of Ningxia University(Natural Science Edition),2005,26(3):211-215. |
| |
| Authors: | Chen Xiuhong |
| |
| Institution: | Department of Mathematics, Huaiyin Normal College, Huaian 223001, China |
| |
| Abstract: | 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. |
| |
| Keywords: | flowshop setup time removal time process time total tardiness approximation algorithm brance and bound method |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
