生产运作管理--第十一章_流水作业的排序问题

《生产运作管理--第十一章_流水作业的排序问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十一章流水作业的排序问题一、排序问题的基本概念排序是确定工件（零部件）在一台或一组设备上加工的先后顺序。在一定约束条件下，寻找总加工时间最短的安排产品加工顺序的方法，就是生产作业排序。例如，考虑32项任务（工件），有32！2.61035种方案,假定计算机每秒钟可以检查1billion个顺序,全部检验完毕需要8.41015个世纪。如果只有16个工件,同样按每秒钟可以检查1billion个顺序计算,也需要2/3年。以上问题还没有考虑其他的约束条件,如机器、人力资源、厂房场地等，如果加上这些约束条件，所需要的时间就无法想象了。所以，很有必要去寻找一些有效算法，解

2、决管理中的实际问题。排序困难性假设条件1.一个工件不能同时在几台不同的机器上加工。2.工件在加工过程中采取平行移动方式，即当上一道工序完工后，立即送下道工序加工。3.不允许中断。当一个工件一旦开始加工，必须一直进行到完工，不得中途停止插入其它工件。4.每道工序只在一台机器上完成。5.工件数、机器数和加工时间已知，加工时间与加工顺序无关。6.每台机器同时只能加工一个工件。排序常用的符号Ji----工件i，i=1,2,..n。Mj----机器j，j＝1，2，…，m.di----工件Ji的完工期限。pij----工件Ji在机器Mj上的加工时间,j=1,…,mPi----

3、工件Ji的加工时间,wij----工件Ji在机器Mj前的等待时间,j=1,…,mWi----工件Ji在加工过程中总的等待时间,Ci----工件Ji的完成时间,Fi----工件Ji的流程时间，即工件在车间的实际停留时间，在工件都已到达的情况下,Fi=Pi+WiLi----工件Ji的延误时间,Li=Ci-di,Li<=0按期或完成提前；Li>0延误Fmax----最长流程时间，Fmax＝max{Fi}二、排序问题的分类和表示法1、排序问题的分类：根据机器数的多少单台机器的排序问题多台机器的排序问题根据加工路线的特征单件作业排序(JobShop)流水作业排序(FlowS

4、hop)根据工件到达系统的情况静态排序动态排序根据参数的性质确定型排序随机型排序根据要实现的目标单目标排序多目标排序2、排序问题的表示法排序问题常用四个符号来描述:n/m/A/B其中,n-----工件数；m-----机器数；A----车间类型；F=流水型排序，P=排列排序G=一般类型,即单件型排序B-----目标函数三、流水作业排序问题1、最长流程时间Fmax的计算举例：有一个6/4/p/Fmax问题，其加工时间如下表所示。当按顺序S＝（6，1，5，2，4，3）加工时，求Fmax。i123456Pi1Pi2Pi3pi442314245674558755542433

5、1i615243Pi1Pi2Pi3pi4244213544576555857143234最长流程时间的计算271213610121316111520273317223035422125323846最长流程时间的计算举例2i146352Pi1453486Pi2391375Pi3768259Pi45639244912162430714191819223136243234394830354446522、两台机器排序问题两台机器排序的目标是使最大完成时间（总加工周期）Fmax最短。实现两台机器排序的最大完成时间Fmax最短的目标，一优化算法就是著名的约翰逊法(Johnso

6、n’sLaw)。其具体求解过程如下例所示。约翰逊－贝尔曼法则约翰逊法解决这种问题分为4个步骤：(1)列出所有工件在两台设备上的作业时间。(2)找出作业时间最小者。(3)如果该最小值是在设备1上，将对应的工件排在前面，如果该最小值是在设备2上，则将对应的工件排在后面。(4)排除已安排好的工件，在剩余的工件中重复步骤(2)和(3)，直到所有工件都安排完毕。举例AB两台设备完成5个零件的加工任务，每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。设备工件编号J1J2J3J4J5设备A36715设备B28643求解过程由约翰逊法可知，表5-8中最小加工时

7、间值是1个时间单位，它又是出现在设备1上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得：J4-*-*-*-*去掉J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单位，它是出现在设备2上的，所以应将对应的工件J1排在最后一位，即：J4-*-*-*-J1再去掉J1，在剩余的J2、J3、J5中重复上述步骤，求解过程为：J4-*-*-J5-J1J4-J2-*-J5-J1J4-J2-J3-J5-J1当同时出现多个最小值时，可从中任选一个。最后得J4-J2-J3-J5-J1(a)J1-J2-J3-J4-J530AB(b)J4-J2-J3-J5-J126AB比

8、较可以看出