调度问题是组合最优化领域和理论计算机科学领域中的一个重要分支,主要研究将稀缺资源分配给在一定时间内不同任务的问题,分配过程也可以理解为一个决策过程。做决策目的是优化一个或者多个目标,有单机调度,也有多机调度。从输入信息的实时性来看,调度(排序)问题可以被分为离线、在线和半在线三类；从输出结果的精确角度来看,调度问题的算法可被分为精确算法,近似算法(包含启发式算法)。调度问题在实际生活中一直都有广泛应用,比如计算机领域的节能调度,负载平衡调度,作业调度,医院中护士排班调度,运输中的动态车辆调度,生产线上的流水调度,飞机的航班调度,钢铁生产过程中的批作业调度和流水调度等等,因此调度问题一直被人们所广泛关注,并且是很多学者的研究课题。本文分别研究了带缓冲在线平行机调度、单机在线调度、带运输时间的流水调度和离线平行机调度等问题。(1)带缓冲在线平行机调度：文中给出了三个在线算法,并给出算法的竞争比分析,改进了已有的研究成果。文中提出了一个在线算法并证明了在同型机的数量m>51,缓冲区大小为[1.5m]的情况,该算法竞争比为1.5；此外还提出在同型机数量为3的情况只需要6个缓冲区的最优的在线算法,改进了之前需要9个缓冲区的最优在线算法；文中还证明了在同类机的数量和缓冲区的均为m时,将竞争比从2+ε提升到2-1/m+ε,其中m是常数即机器的数量,ε>0且足够小(2)单机在线调度：文中研究了单机调度下带有截至期限的抢占-重启模型,在已知的WAL算法中基础上提出了一个传统启发式算法D-WAL算法,其思想就是同时关注任务和作业的收益大小,分析实验结果显示D-WAL算法在性能上比只关注收益大小的WAL算法要好。(3)带运输时间流水调度：文中考虑了一种特殊情况即所有的工件在机器B上加工时间都相同的时候,针对该种特殊情况可以发现：存在一个最优调度使得每个工件在机器A上的加工时间是非递减的,而且工件执行顺序在机器A上的顺序和在机器B和运输机V是一样的。利用这个性质,文中给出了多项式时间的最优调度算法以及相应的证明。(4)离线平行机调度：本文基于经典的粒子群算法,结合Levy飞行方法优化粒子群算法,提出了LPSO算法。分析实验结果发现Levy飞行方法可以使PSO算法本身容易陷入早熟的劣势得到很显著的缓解,并且同时充分发挥了PSO算法的简便快捷特性。