论文部分内容阅读
生产调度(Scheduling)广泛存在于生产和物流系统中，是典型的组合最优化问题。生产调度根据调度信息的完整性可分为离线调度和在线调度。离线调度是指在调度时刻工件的信息全部可利用，而在线调度是指信息在调度开始执行时还不完全知道，调度的信息是随着调度的执行进程而逐渐给出的。以往在调度领域，研究者主要集中在离线调度问题的研究，而实际生产中经常出现调度的信息不能全部给出。例如，在钢铁企业，钢锭加工过程是一个动态的过程，在调度决策开始时，对钢锭的全部信息还不知道，其信息是随着轧制的进程逐渐给出的。由于在线调度问题的广泛存在性，近年来已成为调度领域的热点研究方向。本文对从流程工业中提炼出的一系列在线批调度问题进行了研究，不但对从工业生产中提炼的连接生产与控制的新型调度问题具有重要的理论意义，而且对流程工业能够实时利用过程监控信息进行合理调度具有重要的实际意义。 由于在线调度一般是NP-hard问题，所以当问题规模比较大时，探讨求解这类问题非常困难或是不可能的。因此通过构造启发式算法获得问题的近优解成为该类问题的主要的研究手段和热点研究方向。启发式算法的近似性能的度量主要有三种方法:最坏情况分析方法、平均情况分析方法和实验分析方法，而其中最坏情况分析方法是比较常用的方法。本文主要采用最坏情况分析方法，研究了从流程工业中提炼出的一系列在线批调度问题，给出一组对应问题的启发式算法，分析了提出的启发式算法的性能，证明对应算法的最坏情况比（在线情况下也称竞争率）。整个研究工作分成如下几个方面: 1)基于列表调度(over list)的两台同构并行机在线批调度问题 考虑在两台同构并行机上的在线批调度问题。将经典在线调度中工件一个接一个地按工件列到达的列表调度，推广为在线批列表调度，即工件以批的方式排成一列，批工件是按列表一个接一个地到达的，只有前一个批中工件完全加工后，才可以对其相邻的后一批中的工件进行调度。调度过程中不允许中断。目标函数是使最大完成时间(makespan)最小。给出了一个在线批启发式算法（BLPT-算法），要求当其中任意机器可利用时，将当前排在前面批中的工件按LPT规则调度。证明了该BLPT-算法的最坏情况比为3/2，并给出了该算法的一个实例。 2)基于到达时间(over time)调度的两台同构并行机在线批调度问题 考虑在两台同构并行机上工件具有到达时间的在线批调度问题。将以往在线调度中每个工件具有到达时间问题，推广为工件以批的方式到达，且每批工件具有不确定的到达时间。一旦机器可以利用，要在当前可以利用的批中选择出合适的批并将其中的工件调度到机器上。调度过程中不允许中断。目标函数是使调度的最大完成时间(makespan)最小。给出了一个批工件具有到达时间的批在线调度RBLPT-算法，即在任意一时刻，当某台机器可利用时，将当前已到达批中全部工件加工时间和最大的批调度到机器上，且将每批中的工件按LPT规则调度到两台同构并行机器上。当这批工件完全加工完成后才可以加工其它批中的工件。利用反证法，通过构造最小反例的方法，对最小反例中最后到达批的特征、完成时间与到达时间性质的分析，证明了算法的最坏情况比为3/2。 3)基于列表方式到达的多台并行机在线批调度问题 考虑多台同构并行机上的在线批调度问题。工件以批的形式排成一个批工件列表。当一个批工件可利用时，将这一批中的工件按机器数量分成若干组，要求在同一组中的工件数量与机器数量相等，只有最后一组中工件数量可以小于机器数;每组中工件可以具有不同的开始加工时间但必须具有相同的完成时间;调度过程中不允许中断。目标函数是使最大完成时间(makespan)最小。针对这一问题的各种情况，通过将批调度与在线调度的结合，提出了一系列在线批调度算法，各算法对于每批中工件均利用LPT规则进行分组调度，利用了矩阵分析手段构造算法所产生调度的最大完成时间及最优算法相应的最大完成时间，给出并证明了相应算法的最坏情况比（竞争率）分别为m/(1+(m-1)ε)，m(1-ε)/(1-mε)，m/(1+gε), m(-1+ε)(-1+εm+mkmin)（-1+ξ2m+mkmax）/(-1+εm)(-1+ε1+g+m+mkmin)(-1+ξm+mkmax) 4)基于列表方式到达的多台并行机半在线的批调度问题 考虑在m台同构并行机上的在线批调度问题。工件是以批方式排成一个批工件列表，每批中的工件只有在其可利用时才得到它的加工时间，且每批中工件的加工时间被限定在一个时间区间内。调度过程中不允许中断。目标函数是使最大完成时间(makespan)最小。针对这一问题，提出了一个在线批启发式列表调度算法，即将工件列表中排在前面的批中工件按LPT规则调度，当某一批中的工件被调度完后，才可以调度与其相邻的下一批中的工件。通过最小反例的方法，证明了算法的竞争率为1+1/m。该结论在m＞2时，使算法的最坏情况比优于Graham提出的LS在线算法的竞争率2-1/m。 5)流水车间的在线批调度问题 考虑两台流水机器上的在线批调度问题。有两台流水机，第一台机器是机器容量为a(a为大于2的整数)的批处理机，第二台机器是机器容量为2的批处理机。每台机器在加工一批工件前，要有一个调整时间，设所有的调整时间相等。批工件以列表方式排成一个批工件列。只有当前一批中的工件在两台流水机上加工完成后，才可以加工排在其后面的第一个批中的工件。当每批工件在第一台批处理机上加工完成后，才可以调度到第二台批处理机上加工，并且在加工的过程中机器不可以中断。每批的加工时间为该批中加工时间最大工件的加工时间。设同一工件在第二台机器上的加工时间为其原加工时间的1/k。针对此问题，提出了一个启发式算法，即对当前可利用批中工件按LPT规则排序，然后依次将工件按照批处理机的容量组成满批进行加工，直到最后一批因工件数量不足可能未构成满批。利用了构造实例方法对算法的最坏情况进行了理论分析，证明了它的最坏情况不会超过2-ε+2/k+2. 针对m台流水车间调度问题，按工件加工的方式为先到先加工方式，给出了一个排列调度算法，并假设在两台流水机器间存在存储空间无限大的缓冲区，提出并证明了算法的一个界为m。 6)基于到达时间批工件具有尺寸大小的在线批调度问题 考虑工件具有尺寸大小，且具有到达时间的在线批调度问题。每次到达一批工件，其到达时间是不确定的，且每批中的工件以列表的方式排列。只知道批中排在前面工件的信息，而对排在其后的工件的信息完全未知情况下对于其中的工件进行装箱。只有当排在前面的工件放入某个箱子后，才知道排在它后面一个工件的信息，从而利用这些信息进行装箱。将装好的箱子调度到批处理机上进行加工。已装箱的工件一旦开始加工，只有当这批工件全加工完成后才可以加工后面箱（批）中的工件（即加工过程不可中断）。目标函数是使最大完成时间最小。针对这一问题，提出一个在线批调度算法，即对于每一到达的批，按先到先调度即FF规则，取一个排在最前面的工件放在一个箱子中直到这批中的工件全部取完为止。将每箱工件作为一批按LPT规则放在批处理机上加工，其中每批的加工时间为该批中工件加工时间最大值。通过构造实例的方法对这一复杂问题的最坏情况进行了分析，问题算法的最坏情况比下界为3/2。