| 基于到达时间两台并行机上在线批调度 |
| |
| 引用本文： | 霍满臣,唐立新.基于到达时间两台并行机上在线批调度[J].控制与决策,2009,24(12). |
| |
| 作者姓名： | 霍满臣 唐立新 |
| |
| 作者单位： | 1. 沈阳工程学院,数学教研室,沈阳110136;东北大学,流程工业综合自动化教育部重点实验室,沈阳110004
2. 东北大学,流程工业综合自动化教育部重点实验室,沈阳110004 |
| |
| 基金项目： | 高等学校学科创新引智计划项目，国家杰出青年科学基金，国家自然科学基金，辽宁省教育厅资助项目 |
| |
| 摘 要： | 考虑两台同构并行机上在线批调度问题．每个批具有不确定的到达时间，一旦机器可以利用，要在当前可以利用的批中选择出合适的批，并将其中的工件调度到机器上，且工件在加工过程中不允许中断．目标函数是使调度的最大完成时间最小．给出了一个批在线调度ＲＢＬＰＴ算法，即选择当前批中加工时间之和最大的批按ＬＰＴ 规则调度．另外，利用反证法，对算法的最坏情况进行了分析．
|
| 关 键 词： | 最大完成时间 最坏情况比 同构并行机 最小反例 加工时间 |
| 收稿时间： | 2008-11-28 |
| 修稿时间： | 2009-4-9 |
On-line batch scheduling with real time on two parallel machines |
| |
| HUO Man-chen,TANG Li-xin.On-line batch scheduling with real time on two parallel machines[J].Control and Decision,2009,24(12). |
| |
| Authors: | HUO Man-chen TANG Li-xin |
| |
| Abstract: | On-line batch scheduling problem on two parallel machines is considered. Every batch has uncertain ready time. Once a machine is available, some batch is determined and the jobs in it are scheduled. Non-preemptive is permitted for processing jobs with objective to minimize makespan. An on-line batch scheduling RBLPT-algorithm is given, choose the batch with the maximum sum of processing time and then schedule by LPT-rule the longest processing time first rule). By contradiction, the worst case is analyzed. |
| |
| Keywords: | Makespan Worst case ratio Identical parallel machine Minimum contrary example Processing time |
| 本文献已被 万方数据 等数据库收录！ |
| 点击此处可从《控制与决策》浏览原始摘要信息 |
