车间作业调度job-shop-scheduling

车间作业调度(jobshopscheduling)汇报人：方梁州制作成员：第三学习小组小组成员：方梁州、周梦萦、尹国庆、侯强、欧阳书法、姜坤、张艳群专业班级：工业工程1202班由贪婪法快速求解法想到的数学模型•背景一个复杂的制造系统不仅可能涉及到成千上万道车间调度工序，而且工序的变更又可能导致相当大的调度规模。解空间容量巨大，N个工件、M台机器的问题包含(N!)M种排列。由于问题的连环嵌套性，使得用图解方法也变得不切实际。传统的运筹学方法，即便在单目标优化的静态调度问题中也难以有效应用。•问题•某重型机械厂产品都是单件性的，其中有一车间共有A，B，C，D四种不同设备，现接受6件产品的加工任务，每件产品接受的程序在指定的设备上加工，其工序与加工周期如下表：（S-设备号、T-周期）工序产品12345678STSTSTSTSTSTSTST1C8A2B4C24D62A4D5B3C43C3D7A15B20A84B7C6D21A1D16C35D10B4C8D4A12C6D16A1B4A7C3D5A2C5A8条件：1、每件产品必须按规定的工序加工，不得颠倒；2、每台设备在同一时间只能担任一项任务。（每件产品的每个工序为一个任务）问题：做出生产安排，希望在尽可能短的时间里，完成所接受的全部任务。要求：给出每台设备承担任务的时间表。注：在上面，机器A，B，C，D即为机器1，2，3，4，程序中以数字1，2，3，4表示，说明时则用A，B，C，D•模型假设1．每一时刻，每台机器只能加工一个工件，且每个工件只能被一台机器所加工，同时加工过程为不间断；2．所有机器均同时开工，且工件从机器i到机器j的转移过程时间损耗不计；3．各工件必须按工艺路线以指定的次序在机器上加工多次；4．操作允许等待，即前一操作未完成，则后面的操作需要等待，可用资源有限。•符号说明Ji-第i个工件（i=1…6）JM-机器顺序阵JM(i,j)表示i工件的第j个操作的机器号Mk-第k台机器（k=1…4）MJ-工件排列阵MJ(i,j)表示i机器上第j次加工的工件号T-加工时间阵T(i,j)为i工件的第j个操作的时间周期C-整个任务完成时间•整理数据整理数据后得到：JM=[CABCD000]T=[824246000][ADBC0000][45340000][CDABA000][3715208000][BCDADC00][7621116300][DBCDACD0][1048412610][ABACDACA][14735258]上述二阵直接从题目得出，而MJ则是我们要求的。•加工时间表1.关于工件的加工时间表：2.关于机器的加工时间表：产品/工件（i）:123456总计Ji总净加工时间（周期）441653544535247Ji加工工序总数（个）54567835机器/设备(j):ABCD总计Mi总净加工时间60427075247Mi加工操作次数10610935•分析由于各产品总净加工时间和各机器总净加工时间之中最大值为75，而总计为247，那么总时间C介于[75，247]。同时各工件加工繁杂程度不一，各机器的任务量也有轻重之别。合理的调度排序是对于节省时间和资源是必要的。希望最优化答案是75，这样达到最小值，如果答案是75，那么意味着机器D不间断工作,直至全部加工任务完成。•贪婪法快速求解如果按照一定规则排序，当多个工件出现“抢占”同一机器的局面的时候,我们可以制定如下的工序安排规则:1.优先选择总剩余时间或总剩余操作较多的工件。（如果出现总剩余加工时间多者总剩余操作数反而较少的情况时,按照程度具体情况具体分析）。2.机器方面来说,尽量避免等待空闲时间，优先考虑剩余净加工时间或者剩余加工总次数较多的机器,尤其是机器D,即倘若能够使机器D不间断工作且其他机器完工时间均不多余75时,那么就可以得到最优解。首先按照最优化时间为75的设想避免D出现等待，排序后得到升以下具体排列顺序。各机器承担任务表为：(其中粗体字为对应工件产品号，括号内为对应时间周期段)操作1操作2操作3操作4操作5操作6操作7操作8操作9操作10A6(1)2(2-5)1(12-13)6(14-20)3(21-35)4(36)5(43-54)6(55-56)3(57-64)6(66-73)B4(1-7)6(8-11)5(12-15)1(16-19)3(36-55)2(56-58)C3(1-3)1(4-11)4(12-17)5(18-25)6(26-28)1(29-52)5(55-60)6(61-65)2(66-69)4(70-72)D5(1-10)3(11-17)4(18-38)5(39-42)6(43-47)2(48-52)4(53-68)1(69-74)5(75)操作1操作2操作3操作4操作5操作6操作7操作8操作9操作10A6(1)2(2-5)1(12-13)6(14-20)3(21-35)4(36)5(43-54)6(55-56)3(57-64)6(66-73)B4(1-7)6(8-11)5(12-15)1(16-19)3(36-55)2(56-58)C3(1-3)4(4-9)1(9-17)5(18-25)6(26-28)1(29-52)5(55-60)6(61-65)2(66-69)4(70-72)D5(1-10)3(11-17)4(18-38)5(39-42)6(43-47)2(48-52)4(53-68)1(69-74)5(75)工序产品12345678STSTSTSTSTSTSTST1C8A2B4C24D62A4D5B3C43C3D7A15B20A84B7C6D21A1D16C35D10B4C8D4A12C6D16A1B4A7C3D5A2C5A8上图为加工周期图（甘特图），标注数字为相应操作的周期，完工时间为第75周期。10371784421644842537524201516316615124238801020304050607080D机器C机器B机器A机器建模•符号说明i：工件代号i=1,2,3……6j：工序号j=1,2,3……8k：机器代号k=1,2,3,4Tijk：工件i的第j道工序在机器k上的加工时间aijk=1工件i的第j道工序在k机器上完成0工件i的第j道工序不在k机器上完成Ykiji’j’=1机器k上工件i的第j道工序先于工件工件I’的第j’道工序加工0机器k上工件i的第j道工序不先于工件工件I’的第j’道工序加工•目标函数工件i的第j道工序在机器k上的加工时间Tijk，进行此次加工的等待时间为Dijk,而对于不同的加工顺序X，将会有不同的Dijk，即：Dijk=f(X)由于机器的物理独立性，所以运行最长时间机器的运行周期为完工时间。目标函数：i=1,2,3,4])(min[)(8,41,1ijkjijiijkDTXC1.每台机器完成工序数≥12.工件i的每道工序都要做，并只在一台机器上做3.对于同一台机器上加工的工件ZjjZiiakijk且；且；]8,1[]6,1[141Zkkanimjijk且；]4,1[1)(11ZkkYYijjkijkiji且；]4,1[1''''•约束5.机器可用性6.物料可用性ZkkDTTYDTjijikjikjijijijkijijiijk且；]4,1[)()(','k''''''',','',ijkjiDTTaDTjikjikjikjikkjijiijkijk,)()(1,')1(')1(')1(41'')1(,；