| 工件可预处理的单台机排序问题 |
| |
| 引用本文： | 魏麒,何勇.工件可预处理的单台机排序问题[J].浙江大学学报(理学版),2006,33(4):383-388. |
| |
| 作者姓名： | 魏麒 何勇 |
| |
| 作者单位： | 1. 浙江大学,宁波理工学院基础部,浙江,宁波,315100;浙江大学,数学系,浙江,杭州,310027
2. 浙江大学,数学系,浙江,杭州,310027 |
| |
| 基金项目： | 国家自然科学基金;高等学校优秀青年教师教学科研奖励计划 |
| |
| 摘 要： | 考虑一个工件可预处理的单机排序问题．要求在所有工件能够按时完工的前提下，使得预处理工件的费用最小，证明了对于一般情况，该问题是NP-难的，并给出了动态规划算法．进一步，得到当每个工件的预处理费用都相同时该问题是多项式可解的，并给出了强多项式时间算法．
|
| 关 键 词： | 单机排序 最优算法 计算复杂性 |
| 文章编号： | 1008-9497(2006)04-383-06 |
| 收稿时间： | 2005-02-22 |
| 修稿时间： | 2005年2月22日 |
Single-machine scheduling with job can be processed in advance |
| |
| WEI Qi,HE Yong.Single-machine scheduling with job can be processed in advance[J].Journal of Zhejiang University(Sciences Edition),2006,33(4):383-388. |
| |
| Authors: | WEI Qi HE Yong |
| |
| Institution: | 1. Ningbo Institute of Technology, Zhejiang University, Ningbo 315100, China; 2. Department of Mathematics, Zhejiang University, Hangzhou 310027, China |
| |
| Abstract: | A single machine scheduling where jobs can be preprocessed before they are scheduled to the machine is considered. The objective is to minimize the cost for preprocessing under the constraint that no job is tardy. The problem is showed to be NP-hard and a pesudo-polynomial time algorithm is presented. For the case that the costs for preprocessing jobs are the same, a strongly polynomial time algorithm is presented. |
| |
| Keywords: | single machine scheduling optimal algorithm computational complexity |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《浙江大学学报(理学版)》浏览原始摘要信息 |
| 点击此处可从《浙江大学学报(理学版)》下载免费的PDF全文 |
|
