制造业作业计划与控制

2024/11/51作业计划问题的基本概念流水作业排序问题单件作业排序问题生产作业控制制造业作业计划与控制2024/11/52一、作业计划问题的基本概念1、编制作业计划（Scheduling）要解决的问题编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间间隔。作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。任务分配排序2024/11/532、排序（Sequencing）概念排序：就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力分配给不同工作任务，使预定目标最优化的问题。

派工：在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单的形式下达到具体的机床和工人。

赶工：是在实际季度已经落后于计划进度时采取的行动。

调度：是作业计划编制以后实施生产控制的一切行动。2024/11/54排序中常用的几个概念工件（Job）：服务对象机器（Machine、Processor）：服务者如：n个零件在机器上加工，则零件是工件，设备是机器；工人维修设备，出故障的设备是工件，工人是机器2024/11/55所以，作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。如：可用（1，6，5，4，3，2）表示加工顺序：J1－J6－J5－J4－J3－J22024/11/56表示方法

一般正规的表示方法为：n/m/A/Bn：工件数；m：机器数；A：车间类型（F、P、G）；B：目标函数2024/11/573、排序问题的分类与表示按机器的种类和数量：单台机器和多台机器的排序问题按工件加工路线：单件作业（Job－shop）排序问题，流水作业（Flow－shop）排序问题。按工件到达车间情况：静态排序问题、动态排序问题按目标函数性质、参数等，也可有其他的分类表示2024/11/58流水车间与单件作业排序问题流水车间排序问题的基本特征：每个工件的加工路线都一样。如车－铣－磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车－铣，有的为铣－磨。不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1-J3-J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。2024/11/59流水作业排序一般来说，排列排序问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。2024/11/510单件作业排序的基本特征每个工件都有独特的加工路线，工件没有一定的流向。2024/11/511二、流水车间作业计划问题1、加工周期的计算最长流程时间Fmax（加工周期）：从第一个工件在在第一台机器上加工起到最好一个工件在最好一台机器上加工完毕为止所经过的时间。假定所有工作的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。2024/11/512计算Fmax的几个假定条件：机器M1不会发生空闲；对其它机器，能对某一工件加工必须具备两个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完成。2024/11/513算例求按（6，1，5，2，4，3）加工时的加工周期2024/11/5142、两台机器排序问题（n/2/F/Fmax）的算法

采用约翰逊（Johnson）算法，这是S.M.Johnson在1954年提出的，其中的是极小化从第一个作业到最后一个作业为止的全部流程时间，以ai表示Ji在M1上的加工时间，以bi表示Ji在M2上的加工时间。每个工作都按M1－>M2的路线加工。Johnson的算法法则是：如果Min（ai，bj）<min（aj，bi），则Ji应该排在Jj之前。约翰逊规则包含以下几个步骤：1、列出每个作业在两台加工中心上的作业时间2、选择最短的作业时间3、如果最短的作业时间来自第一台工作中心，则首先进行这个作业；如果最短的作业来自第二个工作中心，则该作业最后排序4、对剩余作业重复进行上述步骤2、3，直到排序完成。2024/11/5152024/11/5163、一般n/m/p/Fmax问题的启发式算法对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以采用启发式算法求得近优解。

Palmer法关键工件法2024/11/517Palmer法Palmer于1965年对流水作业排序问题提出了按斜度指标排列工件的启发式算法，该算法先定义工件的斜度指标然后将各工件按其斜度指标不增进行排序。2024/11/518关键工件法2024/11/519

三、单件车间作业计划问题1、任务分配问题2024/11/5202024/11/521匈牙利算法2024/11/522第一步

使指派问题的系数矩阵经变换，在各行各列中都出现零元素。①从系数矩阵的每行元素减去该行的最小元素；②从系数矩阵的每列元素减去该行的最小元素；2024/11/523第二步

进行试指派，以寻求最优解。①从只有一个零元素的行开始，给这个0元素加圈，记作◎；然后划去◎所在列的其它0元素，记作Φ。②从只有一个零元素的列开始，给这个0元素加圈，记作◎；然后划去◎所在行的其它0元素，记作Φ。③反复进行①、②步，直到所有的0元素都被圈出和划掉为止。2024/11/524第二步④若仍存在没有划圈的0元素，且同行（列）的0元素至少有两个。从剩有0元素最少的行（列）开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。⑤若◎元素的数目m等于矩阵的阶数n，那么求得最优解。若m<n，则转入下一步。

2024/11/525第三步

作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素，为此按以下步骤进行：①对没有◎的行打√；②对已打√的行中所有含Φ元素的列打√；③再对已打√的列中含◎元素的行打√；④重复②、③，直到得不出新的打√的行、列为止⑤对没有打√的行画横线，打√的列画纵线，这就得到覆盖所有0元素的最少直线数。2024/11/526第三步这里令直线数为L。若L<n，说明需要对矩阵进行变换，可转入第四步；若L＝n，而m<n，则回到第二步④，另行试探。2024/11/527第四步

对矩阵变换的目的在于增加0元素。为此，在没有被直线覆盖的部分中找出最小元素，然后在打√行各元素中都减去这个最小元素，而在打√列的各元素上都加上这个最小元素，从而保证原有0元素不变。这样得到新的矩阵（其与原问题有相同最优解），若得到n个独立0元素，则得到最优解，否则转回第三步重复进行，直到得到最优解。2024/11/5282）N个作业m台工作中心排序2024/11/5292、单件作业排序问题的描述2024/11/5303、一般n/m/G/Fmax问题的启发式算法1）两种作业计划的构成能动作业计划（ActiveSchedule）无延迟作业计划（Non-DelaySchedule）2024/11/5332）启发式算法－优先调度法则2024/11/5342024/11/5352024/11/5362024/11/5372024/11/5382024/11/5392024/11/5402024/11/5412024/11/5422024/11/543四、生产作业控制2024/11/5442、车间作业计划控制的内容和意义20