| 带运输时间和一个不可用约束的两台平行机排序 |
| |
| 引用本文： | 陈伯龙.带运输时间和一个不可用约束的两台平行机排序[J].兰州大学学报(自然科学版),2009,45(4). |
| |
| 作者姓名： | 陈伯龙 |
| |
| 作者单位： | 兰州大学数学与统计学院,兰州,730000;兰州大学大气科学学院,兰州,730000 |
| |
| 基金项目： | 国家自然科学基金项目 |
| |
| 摘 要： | 考虑了两台平行机的排序问题,其中一台机器带有一个固定的不可用约束区间,任务的加工是不可中断的,而且每一个任务带有一个运输时间,目标函数是最小化最大运输完工时间.这个问题是强NP-难的.提出一个最坏情况比是8/5的多项式时间近似算法,并指出这个界是紧界.同时还用动态规划方法求解该问题.
|
| 关 键 词： | 不可用约束 运输时间 最坏情况比 近似算法 动态规划 |
Two parallel machines scheduling with one availability constraint and jobs with delivery times |
| |
| CHEN Bo-long.Two parallel machines scheduling with one availability constraint and jobs with delivery times[J].Journal of Lanzhou University(Natural Science),2009,45(4). |
| |
| Authors: | CHEN Bo-long |
| |
| Institution: | 1;2;1.School of Mathematics and Statistics;Lanzhou University;Lanzhou 730000;China;2.School of Atmospheric Science;China |
| |
| Abstract: | Tow parallel machines scheduling problem was considered where one machine was not available during a fixed time period,the unavailable time period was fixed.Jobs were non-preemptive and each job had a delivery time.The objective was to minimize the time by which all jobs were delivered.The problem was strongly N P-hard.A polynomial approximation algorithm with a worst-case performance ratio of 8/5 is suggested to solve the problem,and the results show that the bound is tight.The problem is also solved by us... |
| |
| Keywords: | non-availability constraint delivery time worst-case ratio approximation algorithm dynamic programming |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
