8制造业作业计划与控制课件

POMPOM作业计划问题的基本概念作业计划问题的基本概念流水作业排序问题流水作业排序问题单件作业排序问题单件作业排序问题生产作业控制生产作业控制制造业作业计划与控制制造业作业计划与控制2024/5/41POMPOM一、作业计划问题的基本概念一、作业计划问题的基本概念1、编制作业计划（、编制作业计划（Scheduling）要解决的问题）要解决的问题编制作业计划实质上是要将资源分配给不同的任务，按照既定的优化目标，确定各种资源利用的时间间隔。作业计划与排序不是一回事，它不仅要确定工件的加工顺序，而且还要确定每台机器加工每个工件的开工时间和完工时间。如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。任务分配任务分配 排序排序2024/5/42POMPOM2、排序（Sequencing）概念排序排序：就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力分配给不同工作任务，使预定目标最优化的问题。派工派工：在作业计划制定以后，按照作业计划的要求，将具体生产任务通过工票或施工单工票或施工单的形式下达到具体的机床和工人。赶工赶工：是在实际季度已经落后于计划进度时采取的行动。调度调度：是作业计划编制以后实施生产控制的一切行动。2024/5/43POMPOM排序中常用的几个概念工件（Job）：服务对象机器（Machine、Processor）：服务者如：n个零件在机器上加工，则零件零件是工件，设备设备是机器；工人维修设备，出故障的设备是工件，工人是机器2024/5/44POMPOM所以，作业排序也就是要确定工件在机器上的加工顺序，可用一组工件代号的一种排列来表示。如：可用（1，6，5，4，3，2）表示加工顺序：J1J6J5J4J3J22024/5/45POMPOM表示方法表示方法 一般正规的表示方法为：n/m/A/Bn：工件数；m：机器数；A：车间类型（F、P、G）；B：目标函数2024/5/46POMPOM3 3、排序问题的分类与表示、排序问题的分类与表示按机器的种类和数量：单台机器和多台机器的排序问题按工件加工路线：单件作业（Jobshop）排序问题，流水作业（Flowshop）排序问题。按工件到达车间情况：静态排序问题、动态排序问题按目标函数性质、参数等，也可有其他的分类表示2024/5/47POMPOM流水车间与单件作业排序问题流水车间排序问题的基本特征：流水车间排序问题的基本特征：每个工件的加工路线都一样。如车铣磨。这里指的是工件的加工流向一致，并不要求每个工件必须在每台机器上加工。如有的工件为车铣，有的为铣磨。不仅加工路线一致，而且所有工件在各台机器上的加工顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1-J3-J2，则表示所有机器都是先加工J1，然后加工J3，最后加工J2。2024/5/48POMPOM流水作业排序一般来说，排列排序问题的最优解不一定是相应流水车间排序问题的最优解，但一般是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。2024/5/49POMPOM单件作业排序的基本特征单件作业排序的基本特征每个工件都有独特的加工路线，工件没有一定的流向。2024/5/410POMPOM二、流水车间作业计划问题1、加工周期的计算最长流程时间Fmax（加工周期）：从第一个工件在在第一台机器上加工起到最好一个工件在最好一台机器上加工完毕为止所经过的时间。假定所有工作的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。2024/5/411POMPOM计算Fmax的几个假定条件：机器M1不会发生空闲；对其它机器，能对某一工件加工必须具备两个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完成。2024/5/412POMPOM算例2024/5/413POMPOM2、两台机器排序问题（n/2/F/Fmax）的算法 采用约翰逊（Johnson）算法，这是S.M.Johnson在1954年提出的，其中的是极小化从第一个作业到最后一个作业为止的全部流程时间，以ai表示Ji在M1上的加工时间，以bi表示Ji在M2上的加工时间。每个工作都按M1M2的路线加工。Johnson的算法法则是：如果Min（ai，bj）min（aj，bi），则Ji应该排在Jj之前。约翰逊规则包含以下几个步骤：1、列出每个作业在两台加工中心上的作业时间2、选择最短的作业时间3、如果最短的作业时间来自第一台工作中心，则首先进行这个作业；如果最短的作业来自第二个工作中心，则该作业最后排序4、对剩余作业重复进行上述步骤2、3，直到排序完成。2024/5/414POMPOM2024/5/415POMPOM3、一般n/m/p/Fmax问题的启发式算法对于一般的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以采用启发式算法求得近优解。Palmer法 关键工件法2024/5/416POMPOMPalmerPalmer法法Palmer于1965年对流水作业排序问题提出了按斜度指标排列工件的启发式算法，该算法先定义工件的斜度指标然后将各工件按其斜度指标不增进行排序。2024/5/417POMPOM关键工件法关键工件法2024/5/418POMPOM 三、单件车间作业计划问题2024/5/419POMPOM2024/5/420POMPOM匈牙利算法匈牙利算法2024/5/421POMPOM第一步第一步 使指派问题的系数矩阵经变换，在各行各列中都出现零元素。从系数矩阵的每行行元素减去该行的最小元素；从系数矩阵的每列列元素减去该行的最小元素；2024/5/422POMPOM第二步第二步 进行试指派，以寻求最优解。从只有一个零元素的行行开始，给这个0元素加圈，记作；然后划去所在列列的其它0元素，记作。从只有一个零元素的列列开始，给这个0元素加圈，记作；然后划去所在行行的其它0元素，记作。反复进行、步，直到所有的0元素都被圈出和划掉为止。2024/5/423POMPOM第二步第二步 若仍存在没有划圈的0元素，且同行（列）的0元素至少有两个。从剩有0元素最少的行（列）开始，比较这行各0元素所在列中0元素的数目，选择0元素少的那列的这个0元素加圈。然后划掉同行同列的其他0元素。可反复进行，直到所有0元素都已圈出和划掉为止。若元素的数目m等于矩阵的阶数n，那么求得最优解。若mn，则转入下一步。2024/5/424POMPOM第三步第三步 作最少的直线覆盖所有的0元素，以确定该系数矩阵中能找到最多的独立元素，为此按以下步骤进行：对没有的行打；对已打的行中所有含元素的列打；再对已打的列中含元素的行打；重复、，直到得不出新的打的行、列为止 对没有打的行画横线，打的列画纵线，这就得到覆盖所有0元素的最少直线数。2024/5/425POMPOM第三步第三步这里令直线数为L。若Ln，说明需要对矩阵进行变换，可转入第四步；若Ln，而mn，则回到第二步，另行试探。2024/5/426POMPOM第四步第四步 对矩阵变换的目的在于增加0元素。为此，在没有被直线覆盖的部分中找出最小元素，然后在打行各元素中都减去这个最小元素，而在打列的各元素上都加上这个最小元素，从而保证原有0元素不变。这样得到新的矩阵（其与原问题有相同最优解），若得到n个独立0元素，则得到最优解，否则转回第三步重复进行，直到得到最优解。2024/5/427POMPOM2 2）N N个作业个作业m m台工作中心排序台工作中心排序2024/5/428POMPOM2 2、单件作业排序问题的描述、单件作业排序问题的描述2024/5/429POMPOM3 3、一般、一般n/m/G/Fmaxn/m/G/Fmax问题的启发式算法问题的启发式算法1）两种作业计划的构成 能动作业计划（Active Schedule）无延迟作业计划（Non-Delay Schedule）2024/5/4302024/5/4312024/5/432POMPOM2 2）启发式算法优先调度法则）启发式算法优先调度法则2024/5/433POMPOM2024/5/434POMPOM2024/5/435POMPOM2024/5/436POMPOM2024/5/437POMPOM2024/5/438POMPOM2024/5/439POMPOM2024/5/440POMPOM2024/5/441POMPOM2024/5/442POMPOM四、生产作业控制四、生产作业控制2024/5/443POMPOM2 2、车间作业计划控制的内容和意义、车间作业计划控制的内容和意义2024/5/444POMPOM3 3、生产工序类型和计划方法、生产工序类型和计划方法2024/5/445POMPOM4 4、常用调度措施、常用调度措施2024/5/446POMPOM2024/5/447POMPOM5 5、车间控制的工具、车间控制的工具 2024/5/448POMPOMB B、各种状态和例外报告、各种状态和例外报告2024/5/449POMPOMC C、输入、输入/输出控制报告输出控制报告2024/5/450POMPOM2024/5/451POMPOM6 6、查询报表、查询报表2024/5/452POMPOM7 7、输出、输出/输入控制输入控制2024/5/453谢谢！