最优流水作业调度问题

0018算法笔记——【动态规划】流水作业调度问题与Johnson 法则1、问题描述：n个作业{1，2，…，n}要在由2台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi。

流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

2、问题分析直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。

在一般情况下，机器M2上会有机器空闲和作业积压2种情况。

设全部作业的集合为N={1，2，…，n}。

S是N的作业子集。

在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。

将这种情况下完成S中作业所需的最短时间记为T(S,t)。

流水作业调度问题的最优值为T(N,0)。

设π是所给n个流水作业的一个最优调度，它所需的加工时间为aπ(1)+T’。

其中T’是在机器M2的等待时间为bπ(1)时，安排作业π(2)，…，π(n)所需的时间。

记S=N-{π(1)}，则有T’=T(S,bπ(1))。

证明：事实上，由T的定义知T’>=T(S,bπ(1))。

若T’>T(S,bπ(1))，设π’是作业集S在机器M2的等待时间为bπ(1)情况下的一个最优调度。

则π(1)，π'(2)，…，π'(n)是N的一个调度，且该调度所需的时间为aπ(1)+T(S,bπ(1))<aπ(1)+T’。

这与π是N的最优调度矛盾。

故T’<=T(S,bπ(1))。

从而T’=T(S,bπ(1))。

这就证明了流水作业调度问题具有最优子结构的性质。

由流水作业调度问题的最优子结构性质可知:从公式（1）可以看出，该问题类似一个排列问题，求N个作业的最优调度问题，利用其子结构性质，对集合中的每一个作业进行试调度，在所有的试调度中，取其中加工时间最短的作业做为选择方案。

流水作业调度问题描述:N个作业｛1,2, ..... ,n｝要在由两台机器M1和M2组成的流水线上完成加工。

每个作业加工的顺序都是先在M1上加工，然后在M2上加工。

M1和M2加工作业i所需的时间分别为ai和bi , 1 < i < n。

流水作业高度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。

可以假定任何任务一旦开始加工，就不允许被中断，直到该任务被完成，即非优先调度。

输入:输入包含若干个用例, 第一行为一个正整数K(1<=K<=1000), 表示用例个数, 接下来K 个用例,每个用例第一个为作业数N(1<=N<=1000)，接下来N行，每行两个非负整数，分别表示在第一台机器和第二台机器上加工时间。

输出:每个用例用一行输出采用最优调度所用的总时间，即从第一台机器开始到第二台机器结束的时间。

样例输入:145 612 24 148 7样例输出:33假定直接按顺序进行完成，则机器1 可以不用考虑，因为作业1 完成后就可以完成作业2,直到作业n,需要的时间为所有作业在机器1上的时间总和。

但是，机器2 上完成的时间呢？机器2上完成的时间显示除了作业在机器2上完成的时间总和, 还要加上等待时间, 即要求先在机器1 上完成后,才能在机器2 上开始。

例如5 612 2两个作业,顺序如下：按顺序,则在机器1 上进行作业1 需要5小时,后进行作业2, 需要12小时,和为17 小时；机器2 上,作业1 只能从第5 小时开始,第11 小时完成,等待了5 小时,等到作业2 在机器1 上完成后(已经是第17时),再完成2小时,共19小时。

机器2的等待时间总计为11 小时。

逆序,在机器1上进行作业2需要12小时,后进行作业1 需要5小时,和为17小时,和前面一样；机器2上，作业2完成后开始，等待了12小时，然后再等3小时开始作业1的6小时, 共计21小时，共等待了15小时。

一、 问题描述给定n 个作业，每个作业有两道工序，分别在两台机器上处理。

一台机器一次只能处理一道工序，并且一道工序一旦开始就必须进行下去直到完成。

一个作业只有在机器1上的处理完成以后才能由机器2处理。

假设已知作业i 在机器j 上需要的处理时间为t[i,j]。

流水作业调度问题就是要求确定一个作业的处理顺序使得尽快完成这n 个作业。

二、 算法分析n 个作业{1,2,…,n}要在由2台机器1M 和2M 组成的流水线上完成加工。

每个作业加工的顺序都是先在1M 上加工，然后在2M 上加工。

1M 和2M 加工作业i 所需要的时间分别为t[i,1]和t[i,2], n i ≤≤1.流水作业调度问题要求确定这n 个作业的最优加工顺序，使得从第一个作业在机器1M 上开始加工，到最后一个作业在机器2M 上加工完成所需的时间最少。

从直观上我们可以看到，一个最优调度应使机器1M 没有空闲时间，且机器2M 的空闲时间是最少。

在一般情况下，机器2M 上会有机器空闲和作业积压两种情况。

设全部作业的集合为},....,2,1{n N =。

N S ⊆是N 的作业子集。

在一般情况下，机器1M 开始加工S 中作业时，机器2M 还在加工其他作业，要等时间t 后才能利用。

将这种情况下完成S 中作业所需的最短时间计为),(t S T 。

流水作业调度问题的最优解为)0,(N T 。

1. 证明流水作业调度问题具有最优子结构设a 是所给n 个流水作业的一个最优调度，它所需要的加工时间为']1),1([T a t +。

其中，'T 是在机器2M 的等待时间为]2),1([a t 时，安排作业)(),......,3(),2(n a a a 所需的时间。

记)}1({a N S -=，则我们可以得到])2),1([,('a t S T T =。

事实上，有T 的定义可知])2),1([,('a t S T T ≥.若])2),1([,('a t S T T >，设'a 是作业集S 在机器2M 的等待时间为]2),1([a t 情况下的一个最优调度。

3.1 简述流水线技术的特点。

（1） 流水线把一个处理过程分解为若干个子过程，每个子过程由一个专门的功能部件来实现。

因此，流水线实际上是把一个大的处理功能部件分解为多个独立的功能部件，并依靠它们的并行工作来提高吞吐率。

（2） 流水线中各段的时间应尽可能相等，否则将引起流水线堵塞和断流。

（3） 流水线每一个功能部件的前面都要有一个缓冲寄存器，称为流水寄存器。

（4） 流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。

（5） 流水线需要有通过时间和排空时间。

在这两个时间段中，流水线都不是满负荷工作。

3.2 解决流水线瓶颈问题有哪两种常用方法？答：细分瓶颈段与重复设置瓶颈段 3.3 有一条指令流水线如下所示：（1）求连续输入10条指令的情况下，该流水线的实际吞吐率和效率。

（2）该流水线的瓶颈在哪一段？请采用两种不同的措施消除此瓶颈。

对于你所给出的两种新的流水线，连续输入10条指令时，其实际吞吐率和效率各是多少？解：（1）2200(ns)2009200)10050(50t )1n (t T maxm1i i pipeline =⨯++++=∆-+∆=∑=)(ns 2201T nTP 1pipeline-==45.45%1154400TP mtTP E m1i i≈=⋅=∆⋅=∑= （2）瓶颈在3、4段。

⏹ 变成八级流水线（细分）850(ns)509850t 1)(n t T maxm1i i pipeline =⨯+⨯=∆-+∆=∑=)(ns 851T nTP 1pipeline-== 58.82%17108400TP mtiTP E m1i ≈=⋅=∆⋅=∑= ⏹ 重复设置部件)(ns 851T nTP 1pipeline-==58.82%1710885010400E ≈=⨯⨯=3.4 有一个流水线由4段组成，其中每当流过第三段时，总要在该段循环一次，然后才能流到第4段。

改进迭代贪婪算法求解可重入流水车间调度问题可重入流水车间调度问题（reentrant flow shop scheduling problem）是指在多工序流水车间中，存在可重入现象的调度问题。

在车间中，每个作业需要按照一定的工序顺序加工，而每个工序都有不同的机器可以完成。

不同于一般流水车间问题，可重入流水车间问题允许同一作业在同一工序上重复进行，增加了调度的复杂性和难度。

迭代贪婪算法是一种常用于解决可重入流水车间调度问题的启发式算法。

它的基本思想是通过多次迭代，每次选择当前局部最优的决策来逐步优化最终调度结果。

然而，传统的迭代贪婪算法存在着一些不足之处，例如容易陷入局部最优解、收敛速度较慢等。

因此，本文将针对这些不足之处进行改进，以求更好地解决可重入流水车间调度问题。

一、改进之处在改进迭代贪婪算法求解可重入流水车间调度问题时，我们可以从以下几个方面进行改进：1. 变异操作策略的引入：传统的迭代贪婪算法只考虑选择当前局部最优解进行迭代更新，但这种策略存在着局限性。

我们可以引入变异操作策略，即在每次迭代中，按照一定概率引入一定程度的随机性，以避免陷入局部最优解。

通过引入变异操作，可以增强算法的全局搜索能力，提高算法的质量和效率。

2. 邻域搜索的扩展：邻域搜索是迭代贪婪算法中的关键步骤。

传统的迭代贪婪算法仅仅根据局部最优解进行邻域搜索，但这种策略可能无法充分探索搜索空间。

我们可以考虑扩展邻域搜索的范围，在搜索过程中引入一定程度的随机性，以增加解空间的探索度。

通过扩展邻域搜索的范围，可以更全面地搜索潜在解，提高算法的全局搜索能力。

3. 优化目标函数的定义：目标函数的定义直接关系到算法求解可重入流水车间调度问题的效果。

传统的迭代贪婪算法通常采用简单的目标函数，例如最小化总加工时间或最大化作业的完工时间。

然而，这样的目标函数并不能充分考虑到车间效率与资源利用率等因素。

我们可以重新定义目标函数，结合车间实际情况和约束条件，以综合考虑多个指标，从而求得更合理、更优的调度结果。

典型车间调度问题的分析与研究车间调度问题是制造业中常见的一种问题，在生产管理中起着至关重要的作用。

此问题的核心是如何合理地安排各个车间的生产任务和设备利用率，以达到优化生产效率、缩短生产周期并降低生产成本的目的。

本文旨在从多个方面介绍车间调度问题的分析与研究。

一、问题描述和分类车间调度问题主要涉及下列问题：1. 单机调度问题该问题是考虑一个单一机器或单一设备的调度问题。

其目标是找到一种机器的调度方案，以使得所有的工作任务在规定的期间内完成，同时，最大限度地利用该机器的生产能力。

单机调度问题通常指能够独立完成的作业。

该问题是考虑由多个机器或设备构成的制造系统的调度问题。

通常情况下，多机调度问题是被分成原始、车间和制造流水线的三个不同的问题进行研究，以应对各自的特点。

3. 制造流水线调度问题生产流水线通常由许多具有不同功能的机器或工作站组成。

优化流水线生产效率的调度问题，在一定程度上依赖于流水线的布局和排列顺序。

通过对每个工作站的工序进行优化，可以达到减少生产周期和提高生产效率的目的。

4. 调度与规划问题此问题是在给定的资源限制下，设计制造系统的调度策略。

制造过程的规划和调度策略在许多情况下都是并存的，因为它们需要相互配合以实现最佳生产效率。

二、常用的调度算法为了解决车间调度问题，通常需要使用一些数学模型和算法进行优化。

下面介绍一些常见的调度算法：1. 遗传算法遗传算法是一种进化算法，通过建立基因编码对调度方案进行进化，以最大限度地优化计划和排程。

该算法通常用于求解复杂的车间调度问题。

2. 蚁群算法蚁群算法是一种模拟蚂蚁走路搜索食物的算法。

该算法是用来优化复杂问题的一种有效的方式。

在车间调度问题中，它被认为是一种有效的算法，因为它具有收敛快、精度高、适应性强等特点。

3. 模拟退火算法模拟退火算法是一种优化算法，通过在较难达到的目标函数中寻找全局最优解，达到优化的效果。

该算法不容易陷入局部最优解，因此在多机调度问题和车间调度问题中得到了广泛的应用。

作业车间调度问题是指如何合理地安排工件在不同工序间的加工顺序，以达到最优的生产效率和成本控制。

针对这一主题，我将从几种常见的模型出发，深入探讨作业车间调度问题，旨在为您提供一篇有价值的文章。

一、传统作业车间调度模型1.1 单机调度模型在单机调度模型中，工件依次经过一个加工机器的加工过程。

我们需要考虑如何安排加工顺序、加工时间等因素，以最大程度地减少工件的等待时间和加工时间，提高生产效率。

1.2 流水车间调度模型流水车间调度模型是指在多台加工机器之间，工件按照特定的加工顺序依次进行加工。

我们需要考虑如何合理安排工件的加工顺序，以减少生产中的瓶颈和待机时间，提高整个流水线的生产效率。

1.3 作业车间调度的经典排序问题这种模型主要关注如何将待加工的工件按照特定的规则进行排序，以便在加工过程中最大程度地降低总加工时间和成本。

以上是传统作业车间调度问题的一些经典模型，它们都是针对不同的生产场景和加工流程所提出的解决方案。

接下来，我将对每种模型进行更深入的探讨，以便更好地理解作业车间调度问题。

二、作业车间调度问题的多种解决方法2.1 基于启发式算法的调度方法启发式算法是一种基于经验和规则的算法，它能够快速、高效地求解作业车间调度问题。

常见的启发式算法包括遗传算法、模拟退火算法等，它们能够在短时间内找到较优的解，并且适用于各种不同规模和复杂度的生产场景。

2.2 基于数学规划的调度方法数学规划方法是指利用数学建模和优化理论，对作业车间调度问题进行严格的数学求解。

通过建立数学模型，我们可以利用线性规划、整数规划等方法，对作业车间调度问题进行最优化求解，得到最优的生产调度方案。

2.3 基于仿真的调度方法仿真方法是指利用计算机模拟生产场景，通过模拟实际的生产过程，找到最优的调度方案。

通过仿真，我们可以更加真实地模拟生产现场的情况，找到最优的生产调度策略，提高生产效率和降低成本。

以上是作业车间调度问题的多种解决方法，它们都能够根据不同的生产场景和需求，找到最优的调度方案。