文摘

我们认为在线调度问题在单个机器上假设所有工作的处理时间 ,在那里 和 。所有工作到随着时间的推移,每个工作和处理时间的到达时间。工作应该首先在单个机器上加工,然后由一些客户的车辆。当车辆的容量是无限的,我们提供一个在线算法最好的竞争比 。当车辆的容量是有限的,也就是说,车辆可以提供最多c一次工作,我们提供另一个最好的在线算法的竞争比 。

1。介绍和问题公式化

生产和分配操作是两个重要的部分在一个供应链;是至关重要的整合这两个部分在一个调度问题。在过去的几年里,与工作交付协调调度问题是一个非常重要的话题。离线版本,最早的研究这个话题是一个由Potts [1]。他们认为单机调度问题最小化最大完工交付时间和提供了一个启发式算法最坏性能比 。更多的论文,读者可以参考(2- - - - - -6]。

在线调度,有三个模型通常被认为是(7]。第一个假设不存在发行日期和到达的工作列表。第二个假设每个工作的处理时间是未知的,直到工作完成。第三个假设每个工作到来。机器闲置时,一个在线算法决定哪一个可用的工作计划,如果有的话。在本文中,我们研究工作的第三种模式随着时间到达。对于一个在线算法 中,我们使用的竞争比 测量的性能 ,一个实例 , 是用来表示客观价值的在线算法生成的时间表吗 和 是离线的客观价值最优时间表。

调度问题的在线版本工作交付,设备和Vestjens8)认为在线单机调度问题。他们提供了一个最好的在线算法的竞争比 。当允许重启,van den ak et al。9)提出了一个最好的在线算法的竞争比 。在线集成生产经销调度问题最小化总加权之和流时间和交付总成本被认为是由Averbakh [10]。几个问题的情况下,作者提供了高效的在线算法和竞争分析研究其最糟糕的表现比使用。元等。11]研究了单个批处理机器在线调度问题与限制交货时间;也就是说,每个工作的交付时间是小于或等于其处理时间。他们提供了一个最好的在线算法的竞争比 。为每个工作的情况下,交货时间大于或等于其处理时间,田et al。12)提出了一个最好的在线算法的竞争比 。刘等人。13]研究在线调度问题和有界分布在同一台计算机上。他们证明了所有在线算法的竞争比下界,提出了一个最好的在线算法的竞争比 。刘等人。14]研究在线调度问题在单个机器上日益恶化的就业机会。对于每个模式,他们提出了一个最佳的在线算法。

同时,调度问题的工作长度相等的处理时间是普遍认为;读者可以参考(15- - - - - -17]。然而,更合理的假设的工作处理时间在给定的时间间隔。在半导体制造集成电路生产通过相同的技术流程。因此他们处理时间在给定的时间间隔。方等。18一批机器上]研究在线调度问题假设所有工作的处理时间 ,在那里 和 。的两个调度的问题,他们提供了最好的在线算法的竞争比 。

在本文中,我们研究了单机在线调度问题的工作交付工作的处理时间 ,在那里 和 。工作应该首先在单个机器上加工,然后由一些客户的车辆。当车辆的容量是无限的,我们提供一个在线算法最好的竞争比 。当车辆的容量是有限的,固定的,也就是说,车辆可以提供最多 工作时间和客户 ,我们提供另一个在线算法最好的竞争比 。

2。问题制定和预赛

在单个机器上在线调度问题最小化最大完工交付时间, 工作 随着时间的推移,到达。我们不知道这些工作的任何信息,包括工作岗位的数量和处理时间 和到达时间 每一个工作 。工作是第一个在单个机器上加工。一旦车辆可用,可以立即分批交付完成的工作一些客户的车辆。让 是机器和客户之间的往返运输。因为客户事先是未知的,我们假设 被立即一旦到达的第一份工作。这个问题可以用 。这里的“ ”意味着工作首先在单个机器上加工,然后完成的工作必须分批交付客户;” ”意味着有一个车辆交付工作。” ”是指车辆的容量;” ”意味着就业的处理时间 。我们使用 表示车辆运输的时间 给客户并返回到机器。 表示车辆时完成交付最后一批交货目的地并返回到机器。

实际上,当 和 提前知道,Ng和陆19]提供了一个最佳的在线算法对一般情况下的处理时间每个工作都是一个非负数字。当 和 提前知道,他们提供了一个在线算法并不是最好的。然而,在本文中,我们假设 和 事先是未知的。我们处理两个变量的在线调度问题: 当车辆的容量是无限的 当车辆的容量是有限的,固定的。

让 是一个在线算法生成的时间表 。让 一批交货 。然后我们定义以下符号:(我) 的起始时间 在机 ;(2) 的完成时间 在机 ;(3) ;(iv) ;(v) ;(vi) 的工作是可用的和未加工的时间 ;(七) ,工作的机器上完成,正在等待车辆交付时间 ;(八) ,准备好交货时间批 ,这是最大完工时间的工作分配给批 ;事实上 ;(第九) 、车辆交付批出发的时间 从机器到客户;请注意, 在任何可行的解决方案;(x) 的交付完成时间分批交货 ;(十一)我们说一套交货批次 在此订单不断交付时间表,如果时间间隔 完全是被交付批次的车辆吗 ;同样,我们有 为 ;(十二)假设 在这个订单的交货批次安排;我们说存在车辆直接前的空闲时间 如果一个时间表 ,因为 ;同样,我们说不存在直接前车辆的空闲时间 如果一个时间表 ,因为 。

3所示。一个下界

我们假设 。让 是一个足够小的正数,趋向于零。让 是一个足够大的整数。对于任何在线算法 ,我们考虑以下工作实例生成的对手。让 和 由算法获得的客观价值 分别和离线最优算法。实例中的所有工作有一个处理时间 。让 。在时间 ,敌人释放工作 。假设算法 开始处理 在时间 。如果 到达,然后没有其他工作。显然,我们有 。然而,最优调度的过程 在时间 和交付时间 。然后我们有 。因此, 在以下假设 ;我们假设车辆交付 在时间 。如果 到达,然后没有其他工作。然后我们有 当 。如果 ,然后 到达时间 。显然,我们有 。请注意, 。最优调度过程 在时间 然后交付 和 在一起;也就是说, 。因此,我们有 当 和 。

上述讨论意味着以下两个前题。

引理1。的问题 ,不存在在线算法的竞争比小于 。

引理2。的问题 ,在那里 ,不存在在线算法的竞争比小于 。

4所示。的情况下

在本节中,我们考虑的问题 ,车辆的容量是无限的;也就是说,所有的工作都可以同时在同一批次交付。

算法

处理阶段。在时间 如果机器是可用的和 ,我们选择的工作 最短的处理时间来处理 。否则,只能等待。

交付阶段。在时间 与 ,我们认为 作为一个交付批。如果机器是可用的, , ,我们交付交付批 在时间 。否则,只能等待。

事实上,该算法的处理阶段 是最优的问题吗 ,因为该算法不能产生不必要的空闲时间的机器上。交付阶段,机器可用这意味着没有一个工作是在这个时间和处理 意味着没有一个是可用的和未加工的时间工作 。也就是说,只有在没有一个可用的作业未加工或处理,车辆确定交付。

让 和 由算法生成的时间表 分别和离线最优算法。让 和 目标计划中获取的值 和离线最优时间表 ,分别。让 和 的时间安排 和安排 ,分别。的问题 ,让 是最佳的离线时间。接下来,我们得到以下引理。

引理3。考虑以下

证明。由于算法的处理阶段 机器上不能产生不必要的空闲时间,也就是说,机器总是忙只要有工作是可用的和未加工 。

作为车辆的容量是无限的,我们有以下引理。

引理4。考虑以下

定理5。算法的竞争比 最多是 ;也就是说, 。

证明。让 的交货批次 。集 。假设是最后到达的时间工作 。如果 ,那么我们就有 。因此 ,如需要。在以下假设 。如果 的前题3和4,我们有 如果 ,即交付批 紧跟着后面的交货批 ,那么我们就有 。因此, 作为车辆的容量是无限的,通过算法 ,我们有 。根据该算法 ,我们有 ,尽管 。然后 因此,我们有 。从引理4,(8)可以写成 结果如下。

定理5和引理1暗示 是一个最好的在线算法问题 。事实上,根据定理的证明5, 也是一个最好的在线算法问题 。

5。的情况下

在本节中,我们考虑的问题 ,车辆的容量是有限和固定;也就是说,车辆可以提供最多 工作在相同的批处理一些客户。

算法

处理阶段。在时间 如果机器是可用的和 ,我们选择的工作 最短的处理时间来处理 。否则,只能等待。

交付阶段步骤0。如果车辆闲置, , ,确定 工作岗位的数量 。步骤1。如果 最早,选择完成 的工作 一批交付和交付这批时间 。步骤2。如果 ,然后去以下步骤。一步 。如果机器可用 ,也就是说,没有一个工作是未加工或处理时间 ,我们考虑的工作 一批交付和交付这批时间 。一步 。如果机器很忙 ,也就是说,存在一个未加工或处理在工作时间 ,等到机器和可用 或者下一个到来。步骤3。步骤0。

同样的,该算法的处理阶段 是最优的问题吗 ,因为该算法不能产生不必要的空闲时间。交付阶段,机器可用这意味着没有一个工作是在这个时间和处理 意味着没有一个是可用的和未加工的时间工作 。也就是说,只有如果没有一份工作是未加工或处理车辆确定交付。与此同时,算法意味着较小的工作完成时间不晚于交付与一个更大的完成时间。

让 和 由算法生成的时间表 分别和离线最优算法。让 和 目标计划中获取的值 和离线最优时间表 ,分别。让 和 的时间安排 和安排 ,分别。的问题 ,让 是最佳的离线时间。

随着算法的处理阶段 处理阶段的算法是一样吗 ,我们还有以下引理。

引理6。考虑以下

车辆的容量是有限的和固定的,至少有一个批量交付。让 在安排工作的数量。让 。然后至少有 交货批次在任何可行的时间表。因此下面的引理可观察到。

引理7。考虑以下

一批交货完整的如果它包含 就业机会。否则,它是nonfull。让 的交货批次 。假设是最后到达的时间工作 。

引理8。如果 ,然后 。

证明。作为 ,我们有 。的前题6和7,我们有 接下来的引理。

引理9。如果 和 ,然后 。

证明。请注意, 。根据交付阶段的算法 ,我们有 和 对所有 。然后我们得到 。因此, 接下来的引理。

引理10。如果 和 ,然后 。

证明。让 最早交货批等 持续交付批处理 。如果 ,因为 ,我们有 ;然后 ,如需要。
如果 和 ,因为 ,我们有 。然后 因此,我们有 ,如需要。在以下假设 和 。然后 紧跟着后面的交货批 ,所以 。现在,有两种可能性要讨论。
案例1。有一些nonfull交货批次 。表示前最后nonfull交付批 通过 ,在那里 。显然,我们有 和 。作为 nonfull,由算法 ,我们有 和没有工作的处理时间 。然后,为每个 的工作 到达后 。请注意, 充满交货批次。因此,我们有 从(15)和(16),我们有 是必需的。
案例2。在 ,所有的交货批次 都满了。作为 ,我们有 。从引理7,我们有 。
例2.1 ( )。然后 和 。因为所有的交货批次 是完整的,我们有什么 。然后 ,如需要。
例2.2 ( )。的工作 在这个区间处理的机器上 。请注意, 是最早交货批这样吗 持续交付批处理 。然后有一个空闲时间车辆直接 。然后 。由算法 与更小,工作完成时间不晚于交付,与一个更大的完成时间;然后 。注意的是, 我们有,持续交付批吗 。然而, ,尽管 , 是完整的;我们有 因此,我们有 如果存在一个空闲时间 在机 ,假设 是最早的时候,不存在空闲时间 ,在那里 。然后 到达时间的一些工作。由算法 ,所有的工作 到达或之后 。假设有 工作处理的 的机器上,在那里 。注意的是, 是完整的,那么至少有吗 到达或之后的工作 。事实上,这些工作至少需要 交货批次交付。因此,我们有 作为 ,尽管 ,我们有 从(19),(20.)和(21),我们有 是必需的。
如果不存在空闲时间 在机 ,假设 是最早的时候,不存在空闲时间 。很明显, 和 到达时间的一些工作。由算法 ,所有的工作 到达或之后 。假设有 到达或之后的工作 还有 机器上加工的工作 ,在那里 。还有 机器上加工的工作 。作为 ,我们有 让 ,在那里 和 。然后 此外, 工作处理的 是由 交货批次,因为这些工作是在交付 。然后 ;也就是说, 。因此, ;也就是说, 另一方面, ,我们有 ;然后 ;也就是说, 现在,从(23),(24)和(25),我们有 如果 ,因为 ,我们有 ,如需要。如果 立即,然后不存在空闲时间 的机器上。的工作与一个较小的完成时间不晚于交付,在更大的完成时间,我们有 。此外,存在车辆前的空闲时间 ;然后 ,这意味着 然而, 从(24),(26),(28)和(29日),(27)可以写成 这就完成了证明。

定理11。的问题 车辆的容量是有限的和固定的, 是最好的在线算法的竞争比 。

证明。的前题8,9,10,在线算法的竞争比 是 。结果从引理2。

利益冲突

作者宣称没有利益冲突有关的出版。

确认

这项工作是自然科学基金(批准号江西省20142 bab211017)和学校课题(批准号江西财经大学06162015)。