| 工件具有加工位置上限最小化加权总误工量的单机排序问题 |
| |
| 引用本文： | 陈如冰,原晋江.工件具有加工位置上限最小化加权总误工量的单机排序问题[J].运筹学学报,2010,24(2):131-144. |
| |
| 作者姓名： | 陈如冰 原晋江 |
| |
| 作者单位： | 郑州大学数学与统计学院, 郑州 450001 |
| |
| 基金项目： | The National Nature Science Foundation of China (Nos. 11671368, 11771406, 11971443) |
| |
| 摘 要： | 考虑工件具有加工位置上限最小化总加权误工量的单机排序问题.在此排序问题中，每个工件Jj都具有一个加工位置上限kj.也就是说，如果工件Jj是一个可行排序中的第x个工件，那么就需要满足x ≤ kj.证明了（i）当工件具有相同工期时，该排序问题是二元NP-难的并且是拟多项式时间可解的，（ii）当工件具有单位权重时，该排序问题是一元NP-难的.
|
| 关 键 词： | 机排序 加工位置上限 NP-难 误工量 |
| 收稿时间： | 2020-02-28 |
Single-machine scheduling to minimize total weighted late work with positional due-indices |
| |
| CHEN Rubing,YUAN Jinjiang.Single-machine scheduling to minimize total weighted late work with positional due-indices[J].OR Transactions,2010,24(2):131-144. |
| |
| Authors: | CHEN Rubing YUAN Jinjiang |
| |
| Institution: | School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China |
| |
| Abstract: | We consider the single-machine scheduling problem to minimize the total weighted late work with positional due-indices. In the problem, each job Jj has a positional due-index kj. That is, if Jj is the x-th job in a feasible schedule, then it is required that x ≤ kj. In this paper, we show that (i) the problem is binary NP-hard and can be solved in pseudo-polynomial-time if all the jobs have a common due date, (ii) the problem is unary NP-hard even if all the jobs have a unit weight. |
| |
| Keywords: | single-machine scheduling positional due-indices NP-hard late work |
|
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
