流水线调度排单技巧

流水线作业排序问题/productioncontrol/200908091604.html流水作业排序问题的基本特征是每个工件的加工路线都一致。

在流水生产线上制造不同的零件，遇到的就是流水作业排序问题。

我们说加工路线一致，是指工件的流向一致，并不要求每个工件必须经过加工路线上每台机器加工。

如果某些工件不经某些机器加工，则设相应的加工时间为零。

一般说来，对于流水作业排序问题，工件在不同机器上的加工顺序不尽一致。

但本节要讨论的是一种特殊情况，即所有工件在各台机器上的加工顺序都相同的情况。

这就是排列排序问题。

流水作业排列排序问题常被称作“同顺序”排序问题。

对于一般情形，排列排序问题的最优解不一定是相应的流水作业排序问题的最优解，但一般是比较好的解；对于仅有2台和3台机器的特殊情况，可以证明，排列排序问题下的最优解一定是相应流水作业排序问题的最优解。

这里只讨论排列排序问题。

但对于2台机器的排序问题，实际上不限于排列排序问题。

一、最长流程时间Fmax的计算这里所讨论的是n／m／P /Fmax，问题，其中n为工件数，m为机器数，P表示流水线作业排列排序问题，Fmax为目标函数。

目标函数是使最长流程时间最短，最长流程时间又称作加工周期，它是从第一个工件在第一台机器开始加工时算起，到最后一个工件在最后一台机器上完成加工时为止所经过的时间。

由于假设所有工件的到达时间都为零(ri=0，i= 1，2，…，n)，所以Fmax等于排在末位加工的工件在车间的停留时间，也等于一批工件的最长完工时间Cmax。

设n个工件的加工顺序为S＝(S1，S2，S3，…，Sn)，其中Si为第i位加工的工件的代号。

以表示工件Si在机器M k上的完工时间, 表示工件Si在Mk上的加工时间，k= 1，2，…，m；i=1，2，…，n，则可按以下公式计算：在熟悉以上计算公式之后，可直接在加工时间矩阵上从左向右计算完工时间。

下面以一例说明。

例9．4 有一个6／4／p／F max问题，其加工时间如表9—6所示。

流水作业调度一、 可行性分析与项目开发计划ｎ个作业}{n ,...2,1要在由2台机器M1和M2组成的流水线上完成加工。

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

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

直观上，一个最优调度应该使得机器M1没有空闲时间，而且机器M2的空闲时间最少，在一般情况下，机器M2上会出现机器空闲和作业积压两种情况。

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

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

将这种情况下完成S 中作业所需要的最短时间记做T(S,t),则流水作业调度问题的最优值就是T(N,0).我们通过分析可以知道流水作业调度问题具有最优子结构的性质，因此考虑用动态规划算法自后向前来解决其最优问题。

这就需要通过建模来得出最优子结构的递归式子，从而设计算法求解最优值。

二、 需求分析1、 用户可以根据自己的需要输入想要进入流水线的作业数。

2、 用户可以输入这几个作业在机器M1和M2上的加工时间。

3、 由主函数调用流水作业调度的Johnson 算法来实现对流水作业的安排。

4、 输出经过Johnson 算法安排后的作业序列，这就是最终的一个最优调度。

三、 概要设计 总体设计：假定这n 个作业在机器M1上加工时间为i a ,在机器M2上加工时间为i b ，1<=i<=n. 由流水作业调度问题具有最优子结构性质可知，)}},{(min{)0,(i i b i N T a N T =+= 1<=i<=n 推广到一般情况下，})}0,m a x {},{({),(i a t b i S T a t S T i i -+-+= S i ∈ 式子中，}0,max{i a t -这一项是由于在机器M2上，作业i 必须在},max{i a t 时间之后才能开工，因此，在机器M1上完成作业加工i 之后，在机器还需要}0,max{},max{i i i i i a t b a a t b -+=-+时间完成对作业i 的加工。

工厂生产排程与调度算法分析随着生产自动化水平的提高，工厂的生产排程与调度变得越来越重要。

正确的排程与调度可以极大地提高生产效率，降低成本，增加利润。

因此，工厂生产排程与调度算法成为了一个研究热点。

本文将从调度算法的角度来分析工厂生产排程与调度。

一、调度问题的定义所谓调度，指的是将一定数量的任务分配到一定数量的处理器上，以使得完成这些任务的时间最短或机器利用率最高。

调度问题可分为两类：流水车间调度和非流水车间调度。

所谓流水车间调度，是指生产线作业的排程问题；所谓非流水车间调度，是指无工序前后关系(即两个任务之间与其顺序无关)的多机调度问题。

二、调度算法相应地，调度算法也可分为两类：流水车间调度算法和非流水车间调度算法。

其中，流水线调度算法又可分为单机和多机两类。

2.1 单机调度算法在单机调度算法中，任务的完成时间是由单个机器完成的时间决定的。

其中，最短工序时间优先算法(SPT)是目前最常用的单机调度算法之一。

其算法思路如下：首先，按照任务的工序时间大小排序，选择工序时间最短的任务，将它分配给机器；然后重复以上操作，知道所有任务都被分配完毕。

SPT算法具有简单、易实现的特点，同时在任务处理数量较小时也能够得到不错的效果。

2.2 多机调度算法在多机调度算法中，多个机器同时处理任务，任务的完成时间取决于处理速率最慢的机器。

而且，多机调度算法所涉及到的问题，一般都有前后件关系。

解决多机调度算法需要的算法有很多，比如距离平方优先算法(DDU)、加权费用的扩展岛算法(EI)、加权条带算法(applying Weighted Strip Packing, AWSP)等。

其中，DDU算法是一种启发式算法，根据任务的层级和距离来构造解的空间，然后搜索这个空间；EI算法是应用动态规划的思想，拉直排成长条，将任务分配到短条上去完成；AWSP算法则是基于贪心思路，优先将最紧急的任务分配到可处理它们的机器上。

三、调度实践上述调度算法可以用于实践中。

第十一讲流水线操作技术一、流水线操作二、延迟分支转移的流水线图三、条件招待指令的流水线图：四、双寻址存储器的流水线冲突五、流水线的冲突问题指令字、单字指令、双字指令、多字指令：指令字：表征指令的二进制代码，由操作码和操作数组成单字指令：由16位二进制代码表示的指令（1个字）双字指令：由32位二进制代码表示的指令（2个字）多字指令：由n*16位二进制代码表示的指令（n个字）说明：1）执行一条单字指令至少需要1个指令周期（6个机器周期）2）执行一条双字至少指令需要2个指令周期3）程序执行时只能依次取出一个指令字，不能同时取出两个指令字1）一般在一条指令中操作码占8位，其余为操作数位2）若操作数不超过8位则为单字指令，否则为双字指令或多字指令3）立即数寻址为单字（立即数为3、5、8位），双字（9、16位）4）绝对地址寻址为双字指令5）累加器寻址为单字（*ARx)或双字(#lk)指令6）直接寻址为单字指令7）间接寻址为单字指令9）存储器映象寄存器寻址为单字指令10）堆栈寻址为单字指令双操作数间接寻址的指令格式：单字指令机器周期、指令周期、1个机器周期1个指令周期基于流水线的存储器访问：二、延迟分支转移的流水线图：取出要转移的地址完成转移知道要转移得到转移的地址将要转移的地址加载PAB执行转移只需2个周期实现转移浪费2个周期开始执行转移实际使用4个周期1）被冲洗掉的两个单周期指令并不占用转移后指令的执行阶段，它们刚好是在各级错开的。

2）在6级流水线中执行双字分支转移转移指令必须要4个机器（即4个指令周期）周期才能完成，在满流水线中执行相当于只占用2个指令周期（机器周期），另外2个周期可用于完成两条单周期指令或一条双周期指令的执行。

3）采用延迟分支转移指令可利用转移指令后的两个周期，即在延迟分支转移指令后安排两条单周期或一条双周期指令，该指令不能是分支或重复指令。

4）具有延迟操作功能的指令有：BD FBD BACCD FBACCD BANZD CALLD CALLD FCALLD FCALLD RETD FRETD RETED FRETED RETFD FRETD CCD RCD例3-9 在完成R=（x+y)*z操作后转移至next r的程序段有两种编写方式：利用普通分支转移指令BLD @ x , AADD @ y , ASTL A , @ sLD @ s , TMPY @ z , ASTL A , @ RB next共8个指令字，10个指令周期利用延迟分支转移指令BD LD @ x , AADD @ y , ASTL A , @ sLD @ s , TBD nextMPY @ z , ASTL A , @ R共8个指令字，8个指令周期利用普通分支转移指令B LD @ x , A ADD @ y , ASTL A , @ sLD @ s , T MPY @ z , ASTL A , @ RB next共8个指令字，10个指令周期LD @ x , AADD @ y , ASTL A , @ sLD @ s , TMPY @ z , ASTL A , @ RB next完成转移1 2 3 4 5 6 7 8 9 10 11 12 13 14 15LD @ x , AADD @ y , ASTL A , @ sLD @ s , TMPY @ z , ASTL A , @ RBD next完成转移1 2 3 4 5 6 7 8 9 10 11 12 13 14 15利用延迟分支转移指令BD LD @ x , A ADD @ y , A STL A , @ s LD @ s , T BD next MPY @ z , A STL A , @ R 共8个指令字，8个指令周期三、条件招待指令的流水线图：条件招待指令：XC n , cond [ , cond , [ ,cond ]]求解条件决定后面指令是否执行1）条件执行指令是一条单字单周期指令，比条件跳转指令快。

生产调度的技巧
1. 有效的沟通和协作：生产调度需要与各个部门以及供应商进行有效的沟通和协作，确保生产计划的顺利执行。

2. 数据分析和预测：通过对历史数据和市场趋势的分析，预测需求量和生产能力，以便制定合理的生产计划。

3. 灵活的排程：考虑到订单变化、原材料供应延迟等因素，需要灵活地调整生产计划和排程。

4. 风险管理：对生产调度过程中可能出现的风险进行评估和管理，制定相应的预案和措施。

5. 制定优化方案：通过工艺改进、设备升级等措施，优化生产调度，提高生产效率和降低成本。

6. 追踪和监控：对生产进度、资源利用情况进行实时追踪和监控，及时发现并解决问题。

7. 精细化管理：对生产过程进行细致的管理，确保各个环节的顺利衔接，避免生产瓶颈和浪费。

8. 培训和激励：培训生产调度人员的专业技能和管理能力，激励他们积极参与工作，提高生产调度的效能。

一、 问题描述给定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 情况下的一个最优调度。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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