| 带广义偏序约束的Flow—shop排序问题 |
| |
| 引用本文： | 杜东雷 韩继业. 带广义偏序约束的Flow—shop排序问题[J]. 应用数学学报, 1997, 20(4): 587-592 |
| |
| 作者姓名： | 杜东雷 韩继业 |
| |
| 作者单位： | 中国科学院应用数学所，中国科学院应用数学所 北京，100080，北京，100080 |
| |
| 摘 要： | 本文研究了一种新的排序问题：带“广义偏序”约束的ｆｏｌｗ－ｓｈｐｏ排序问题。如工件Ｊｊ与工件Ｊｋ之间有广义偏序，则Ｊｊ→Ｊｋ，且Ｊｊ的完工时间与Ｊｋ的开工时间的间隔洋小于ｌｊｋ和不大于ｕｊｋ，０≤ｌｊｋ≤ｕｊｋ。问题的目标函数是最大完工时间。
|
| 关 键 词： | Folw－shop排序 广义偏序 排序 流水作业问题 |
FLOW-SHOP SCHEDULING WITH GENERALIZED PRECEDENCE CONSTRAINTS |
| |
| DU DONGLEI, HAN JIYE. FLOW-SHOP SCHEDULING WITH GENERALIZED PRECEDENCE CONSTRAINTS[J]. Acta Mathematicae Applicatae Sinica, 1997, 20(4): 587-592 |
| |
| Authors: | DU DONGLEI HAN JIYE |
| |
| Abstract: | A new kind of flow-shop scheduling problem, flow-shop with generalized precedeuce constraints, is considered in this paper. When task Jjprecedes task Jk, the time between the end of task Jj and the beginning of task Jk must be at least ljk, but no more than ujk, where 0 ljk ujk. The objective is to minimize makespan. For some precedence relations, the problem is shown to be NP-hard, and some heuristics are given with worst-case analysis. For some special cases, polynomial algorithms are offered. |
| |
| Keywords: | Flow-shop scheduling generalized precedence makespan heuristics |
| 本文献已被 CNKI 维普 等数据库收录！ |
