| 加工时间可控和简单线性增长的平行机排序 |
| |
| 引用本文： | 周伟刚,高成修,黄凯.加工时间可控和简单线性增长的平行机排序[J].应用数学学报,2010,33(4). |
| |
| 作者姓名： | 周伟刚 高成修 黄凯 |
| |
| 作者单位： | 1. 襄樊学院数学与计算机科学学院,襄樊,441053
2. 武汉大学数学与统计学院,武汉,430072 |
| |
| 基金项目： | 国家自然科学基金，襄樊学院规划 |
| |
| 摘 要： | 本文研究加工时间可控并随开工时间简单线性增长的平行机排序问题.证明了该问题为NP-难问题,该问题存在满足以下性质的最优排序:每个工件的加工时间要么完全压缩,要么完全不压缩;每台机器的工件排序由一个工件参数和控制变量的函数的递增序给出.通过将问题等价转换为0-1非线性整数规划问题,给出了平行机排序问题的贪婪算法.
|
| 关 键 词： | 平行机排序 可控的加工时间 恶化的加工时间 0-1非线性整数规划 贪婪算法 |
Parallel Machine Scheduling with Controllable and Simple Linear Increasing Processing Times |
| |
| ZHOU WEIGANG,GAO CHENGXIU,HUANG KAI.Parallel Machine Scheduling with Controllable and Simple Linear Increasing Processing Times[J].Acta Mathematicae Applicatae Sinica,2010,33(4). |
| |
| Authors: | ZHOU WEIGANG GAO CHENGXIU HUANG KAI |
| |
| Institution: | ZHOU WEIGANG (School of Mathematics and Computer Science,Xiangfan University,Xiangfan 441053) GAO CHENGXIU HUANG KAI (School of Mathematics and Statistics,Wuhan University,Wuhan 430072) |
| |
| Abstract: | This paper considers a parallel machine total weighted completion time scheduling problem with controllable and simple linear increasing processing times.We prove that for this NP-hard problem,there exists an optimal solution such that the processing time of each job is either fully reduced or not reduced at all,and for every machine,the optimal job sequence is defined by the increasing order of a certain function of the parameters and control decision of each job.By formulating the problem as a 0-1 nonline... |
| |
| Keywords: | parallel machine scheduling controllable processing time deteriorating processing time 0-1 non-linear programming greedy algorithm |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
