单机调度问题的复杂性.pdfVIP

第 17 卷 第 4 期 华　东　交　通　大　学　学　报 V o l. 17　N o. 4 2000 年 12 月 Jou rn a l o f E a st Ch in a J iao ton g U n iver sity 　D ec. 　2000 　　文章编号:(2000) 单机调度问题的复杂性 1 2 3 林淑容 , 　周荷芳 , 　周贤伟 ( 1. 四川农业大学 基础课部, 四川 雅安　6250 14; 2. 西南交通大学 交通运输学院, 四川 成都　6 1003 1; 3. 北方交通大学 电子信息工程学院, 北京　100044) 摘要: 研究一类单台机器具有速度可选择约束的调度问题, 这在车辆调度和通信调度中具有广 泛的应用, 以进一步研究交通和通信中的拥挤和堵赛问题 引进了有关记号, 提出了有关的新 概念并给出了该问题解的有关性质, 对单台机器问题的有关多项式情形算法进行了论证 关　键　词: 单台机器; 速度; 调度; 算法 中图分类号: O 22 1 　　　文献标识码: A 0　引　言 　　调度问题是一个成果丰富的研究领域, 其模型在生产作业安排、车辆调度、通信网络等方 [ 1, 2 ] ( ) 面都有广泛的应用 有时根据不同的要求, 加工一零件 泛指任务、计划单元 时还需要附加 的资源如设备、人力、资金等, 这说明了通过增加或减少附加的资源在较短或较长的持续时间 以内加工完一零件[3, 4 ] 本文研究了每当加工一零件时, 该零件通过对机器不同加工速度的选 择而产生不同的附加费用 　　主要结果: 对单机器情形问题 1 sp e. Cj 和问题 1 sp e. w j Cj 都具有多项式时间算 ∑ ∑ 法, 但对多台机器情形计算复杂性尚未解决 1　问题的提出 　　设有 个相互独立的零件, 其零件集 = { 1 , …, n }, 有 台机器 1 , 2 , …, m , 记为 n J J J m M M M M = { , , …, }, 零件 在 上的标准加工时间为 ( ) = 1, M 1 M 2 M m J i M j P j i 机器速度为 1 的加工时间 , i 2, …, 零件 在机器 上加工时的单位速度费用为 ( 0) , 加工时间为 , 可选 n J i M j ej i ej i P j i x j i x j i 取 , , …, 之一, 将机器 的速度集合记为 , 即 ∈ 问怎样选取速度 , 且给零 vj i1 vj i2 vj ik M j j , x j i j x j i 件安排一加工顺序可使指定的目标函数得到最优