单机调度问题的复杂性

研究一类单台机器具有速度可选择约束的调度问题 ,这在车辆调度和通信调度中具有广泛的应用 ,以进一步研究交通和通信中的拥挤和堵赛问题 .引进了有关记号 ,提出了有关的新概念并给出了该问题解的有关性质 。

单台机器速度可选择的排序问题

研究一类单台机器具有速度可选择约束的排序问题。引进了有关记号，给出了该问题解的概念。ｍ＝１的情形问题１｜ｓｐｅ．｜ΣＣ＿ｊ和问题１｜ｓｐｅ．｜Σｗ＿ｊＣ＿ｉ具有多项式时间算法，即为所谓的Ｐ问题，但对ｍ为一般情形其计算复杂性尚未解决。