单机调度问题的复杂性  

Complexity of Single Machine Scheduling Problems

作　　者：林淑容[1] 周荷芳[2] 周贤伟[3] 

机构地区：[1]四川农业大学基础课部,四川雅安625014 [2]西南交通大学交通运输学院,四川成都610031 [3]北方交通大学电子信息工程学院,北京100044

出　　处：《华东交通大学学报》2000年第4期79-82,共4页Journal of East China Jiaotong University

摘　　要：研究一类单台机器具有速度可选择约束的调度问题 ,这在车辆调度和通信调度中具有广泛的应用 ,以进一步研究交通和通信中的拥挤和堵赛问题 .引进了有关记号 ,提出了有关的新概念并给出了该问题解的有关性质 。This paper studies scheduling problems of a type of single machine with selectable machine speeds,which are quite common in bus and communications scheduling.Thus a congesting and jamming model of traffic is studied.Marks are introduced new concept is put forward and some properties of solution are given.Polynomial case algorithm of single machine is proved.In the case of m =1,polynomial algorithms are presented.

关 键 词：单台机器 速度 调度问题 算法 复杂性 

分 类 号：O224[理学—运筹学与控制论]