ch作业计划与控制.pptVIP

第11章 作业计划与控制Operations Scheduling and Controlling 第1节 基本概念 1 排序(sequencing)与编制作业计划(scheduling)的差别 排序，给出零部件在一台或一组设备上加工的先后顺序 编制作业计划，不仅包括零部件的加工顺序，还包括机器加工每个零部件的开始时间和完成时间 所以,编制作业计划与排序的概念和目的都是不同的 但是，编制作业计划的主要工作之一就是要确定出最佳的作业顺序 单件车间制定作业计划示意图 确定出最佳的作业顺序看似容易，只要列出所有的顺序，然后再从中挑出最好的就可以了，但要实现这种想法几乎是不可能的。 例如，考虑32项任务（工件），有32！?2.6?1035种方案,假定计算机每秒钟可以检查1 billion个顺序, 全部检验完毕需要8.4?1015个世纪. 如果只有6个工件, 同样按每秒钟可以检查1 billion个顺序计算, 也需要2/3年. 以上问题还没有考虑其他的约束条件, 如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。 所以，很有必要去寻找一些有效算法，解决管理中的实际问题。 2 排序问题的分类 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 根据加工路线的特征 单件车间排序(Job Shop)——工件加工路线不同 流水型排序(Flow Shop)——工件加工路线相同 根据工件到达系统的情况 静态排序——都到达后，一次性排序 动态排序——陆续到达，随时排序 根据参数的性质 确定型排序——加工时间等参数已知 随机型排序——参数未知 根据要实现的目标 单目标排序 多目标排序 3 排序问题的表示方法 排序问题常用四个符号来描述: n/m/A/B 其中, n-----工件数； m-----机器数； A----车间类型, F=流水车间排序 P=排列排序 G=一般单件车间排序 B-----目标函数 5 排序常用的符号 Ji----工件i，i=1,2,.…n Mj---机器j, j=1,2……m Pi----工件i的加工时间, , pij----工件i在机器j上的加工时间,j=1,…,m 4 假设条件： 一个工件不能同时在几台不同的机器上加工 工件在加工过程中采用平行移动方式 不允许中断（区别于“不允许等待”） 每道工序只在一台机器上完成 工件数、机器数和加工时间已知 每台机器同时只能加工一个工件 补充：生产过程组织中的零件移动方式 1、基本含义 所谓零件移动方式，就是零件在上道工序加工完毕后，是整批地移动到下道工序，还是立即移动到下道工序，即零件在生产过程中的运送组织方式问题。 不同的移动方式，对生产运作的某些绩效指标的影响不同。一般地说，零件的移动方式有三种，即顺序移动、平行移动和平行顺序移动。 2、加工对象（零件）在生产过程中的移动方式 顺序移动方式 物品在加工过程中，在相邻的两个阶段，是整批整批地移动。 优点：设备利用率高；移动次数少 缺点：加工周期长；管理工作复杂 常用于单件或成批生产过程———工艺原则 平行移动方式 物品在加工过程中，在相邻的两个阶段，是一个一个地移动 平行顺序移动方式 既保持一批零件顺序加工；又尽可能使相邻工序加工时间平行进行 T平顺= T顺 ? 重合部分 当t前t后，重合部分(n-1) t前 当t前t后，重合部分(n-1) t后 重合部分(n-1)t短工序 第2节 流水车间的排序问题 “F”与“P”类型都属于流水车间排序（基本特征：每个工件的加工路线都一致，即工件流向一致） “F”----流水车间排序（流向一致，加工顺序不一定相同） “P”----流水车间排列排序（流向一致，加工顺序一致） 排列排序是流水排序的一种特例 M=2台和3台 ，排列排序的最优解是流水排序的最优解 M≥4, 流水排序未必是排列排序，因为排列排序中可能不包含最优解 1 最长流程时间Fmax的计算 讨论的是n/m/P/Fmax（排列排序问题，目标函数使最长流程时间最短） 最长流程时间又叫加工周期，从第一个工件在第一台机器开始加工算起，到最后一个工件在最后一台机器上完成为止所经过的时间。 假设所有工件的到达时间都为0，即ri