车间生产作业排序(1)

生产(shēngchǎn)作业排序一、基本概念二、最长 流程 快递问题件怎么处理流程河南自建厂房流程下载关于规范招聘需求审批流程制作流程表下载邮件下载流程设计 时间三、n/2/F/Fmax问题的算法(suànfǎ)四、一般n/m/P/Fmax问题的启发式算法(suànfǎ)五、单件车间排序问题第一页，共38页。华中科技大学管理学院一、基本概念1、排序(páixù)排序(páixù)就是要将不同的工作任务安排一个执行的顺序，使预定的目标最优化。实际上就是要解决如何按时间的先后，将有限的人力、物力资源分配给不同工作任务，使预定目标最优化的问题。第二页，共38页。华中科技大学管理学院一、基本概念排序中常用的几个概念工件（Job）：服务对象(duìxiàng)；机器（Machine、Processor）：服务者。如：n个零件在机器上加工，则零件是工件(gōngjiàn)，设备是机器；工人维修设备，出故障的设备是工件(gōngjiàn)，工人是机器。第三页，共38页。华中科技大学管理学院一、基本概念所以，作业排序也就是要确定工件(gōngjiàn)在机器上的加工顺序，可用一组工件(gōngjiàn)代号的一种排列来 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示。如可用（1，6，5，4，3，2）表示加工顺序：J1—J6—J5—J4—J3—J2。第四页，共38页。华中科技大学管理学院一、基本概念2、作业 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 （Scheduling）作业计划与排序不是一回事，它不仅要确定工件的加工顺序(shùnxù)，而且还要确定每台机器加工每个工件的开工时间和完工时间。如果按最早可能开（完）工时间来编排作业计划，则排序完后，作业计划也就确定了。第五页，共38页。华中科技大学管理学院一、基本概念3、排序问题的分类与表示(biǎoshì)1）单台机器与多台机器的排序问题。2）流水车间与单件车间排序问题。第六页，共38页。华中科技大学管理学院一、基本概念流水车间排序问题的基本特征：每个工件的加工(jiāgōng)路线都一样。如车—铣—磨。这里指的是工件的加工(jiāgōng)流向一致，并不要求每个工件必须在每台机器上加工(jiāgōng)。如有的工件为车—磨，有的为铣—磨。不仅加工(jiāgōng)路线一致，而且所有工件在各台机器上的加工(jiāgōng)顺序也一样，这种排序称为排列排序（同顺序排序）。如工件排序为：J1—J3—J2，则表示所有机器都是先加工(jiāgōng)J1，然后加工(jiāgōng)J3，最后加工(jiāgōng)J2。第七页，共38页。华中科技大学管理学院一、基本概念单件车间排序问题的基本特征：每个工件都有其独特的加工路线，工件没有(méiyǒu)一定的流向。第八页，共38页。华中科技大学管理学院一、基本概念3）表示方法一般正规的表示方法为：n/m/A/Bn：工件数；m：机器数；A：车间类型(lèixíng)（F、P、G）；B：目标函数第九页，共38页。华中科技大学管理学院一、基本概念4）一般(yībān)来说，排列排序问题的最优解不一定是相应流水车间排序问题的最优解，但一般(yībān)是比较好的解。而对于仅有2台或3台机器的情况，则排列排序问题的最优解一定是相应流水车间排序问题的最优解。第十页，共38页。华中科技大学管理学院一、基本概念4、排序问题的假设条件一个工件不能同时在几台不同的机器(jīqì)上加工。工件在加工过程中采取平行移动方式。不允许中断。每道工序只在一台机器(jīqì)上完成。每台机器(jīqì)同时只能加工一个工件。工件数、机器(jīqì)数和加工时间已知，加工时间与加工顺序无关。第十一页，共38页。华中科技大学管理学院二、最长流程(liúchéng)时间最长流程时间（加工周期）：从第一个工件在第一台机器(jīqì)上加工起到最后一个工件在最后一台机器(jīqì)上加工完毕为止所经过的时间。假定所有工件的到达时间都为0，则Fmax等于排在末位加工的工件在车间的停留时间。第十二页，共38页。华中科技大学管理学院二、最长流程(liúchéng)时间计算Fmax的几个假定条件：机器M1不会(bùhuì)发生空闲；对其它机器，能对某一工件加工必须具备2个条件：机器必须完成排前一位的工件的加工；要加工的工件的上道工序已经完工。第十三页，共38页。华中科技大学管理学院二、最长流程(liúchéng)时间第十四页，共38页。华中科技大学管理学院二、最长流程(liúchéng)时间ipi1pi2pi3pi4615243255144544453258217533674261012131671115202733121722303542132125323846第十五页，共38页。华中科技大学管理学院三、n/2/F/Fmax问题(wèntí)的算法Johnson算法：假定(jiǎdìng)：ai为工件Ji在机器M1上的加工时间，bi为工件Ji在机器M2上的加工时间，每个工件按M1—M2的路线加工。第十六页，共38页。华中科技大学管理学院三、n/2/F/Fmax问题(wèntí)的算法Johnson算法的步骤：从加工时间矩阵中找出最短的加工时间。若最短时间出现(chūxiàn)在M1上，则对应的工件尽可能往前排。若最短时间出现(chūxiàn)在M2上，则对应的工件尽可能往后排。若最短时间有多个，则任选一个。划去已排序的工件。若所有工件都已排序，则停止，否则重复上述步骤。第十七页，共38页。华中科技大学管理学院四、一般(yībān)n/m/P/Fmax问题的启发式算法对于一般(yībān)的n/m/P/Fmax问题，可以用分支定界法求得最优解，但计算量很大。实际中，可以用启发式算法求近优解。第十八页，共38页。华中科技大学管理学院四、一般n/m/P/Fmax问题(wèntí)的启发式算法1、Palmer法计算工件斜度指标i：m:机器数pik：工件i在机器k上的加工时间(shíjiān)。i=1,2,,n排序方法:按i从大到小的顺序排列。按排序的顺序计算Fmax第十九页，共38页。华中科技大学管理学院四、一般(yībān)n/m/P/Fmax问题的启发式算法2、关键工件(gōngjiàn)法：计算Pi=Pij，找出Pi最长的工件(gōngjiàn)，将之作为关键工件(gōngjiàn)C。对其余工件(gōngjiàn)，若Pi1≤Pim，则按Pi1由小到大排成序列SA。若Pi1>Pim，则按Pim由大到小排成序列SB。顺序（SA，C，SB）即为近优解。第二十页，共38页。华中科技大学管理学院四、一般n/m/P/Fmax问题(wèntí)的启发式算法得到(dédào)的加工顺序为(1，2，3，4)第二十一页，共38页。华中科技大学管理学院四、一般n/m/P/Fmax问题(wèntí)的启发式算法3、CDS法：CDS法是Johnson算法的扩展(kuòzhǎn)方法，从M-1个排序中找出近优解。第二十二页，共38页。华中科技大学管理学院四、一般n/m/P/Fmax问题(wèntí)的启发式算法L＝1，按Johnson算法得到(dédào)加工顺序(1，2，3，4)，Fmax＝28L＝2，按Johnson算法得到(dédào)加工顺序(2，3，1，4)，Fmax＝29取顺序(1，2，3，4）为最优顺序。第二十三页，共38页。华中科技大学管理学院五、单件车间排序(páixù)问题（n/m/G/Fmax）1、问题描述(i，j，k)：表示工件i的第j道工序(gōngxù)是在机器k上进行。加工描述矩阵D：每一行描述一个工件的加工，每一列的工序(gōngxù)序号相同。D=1,1,11,2,31,3,22,1,32,2,12,3,2第二十四页，共38页。华中科技大学管理学院五、单件车间(chējiān)排序问题（n/m/G/Fmax）加工时间矩阵(jǔzhèn)T：与D相对应。D=1,1,11,2,31,3,22,1,32,2,12,3,2T=463574第二十五页，共38页。华中科技大学管理学院五、单件车间排序(páixù)问题（n/m/G/Fmax）加工顺序矩阵S：每一行与机器(jīqì)相对应，每一列与工件相对应。D=1,1,11,2,31,3,22,1,32,2,12,3,2S=1,1,12,2,11,3,22,3,22,1,31,2,3第二十六页，共38页。华中科技大学管理学院五、单件车间(chējiān)排序问题（n/m/G/Fmax）用方块图表示(biǎoshì)：D=1,1,11,2,31,3,22,1,32,2,12,3,2S=1,1,12,2,11,3,22,3,22,1,31,2,3T=4635741,1,12,1,31,2,32,2,11,3,22,3,2M1M2M3第二十七页，共38页。华中科技大学管理学院五、单件车间(chējiān)排序问题（n/m/G/Fmax）2、能动(néngdòng)作业计划的构成各工序都按最早可能开(完)工时间安排且任何一台机器的每段空闲时间都不足以加工一道可加工工序。符号说明：{Ot}第t步可以排序的工序的集合{St}t步之前已排序的工序构成的部分作业计划Tk{Ot}中工序Ok的最早可能开工时间T’k{Ot}中工序Ok的最早可能完工时间第二十八页，共38页。华中科技大学管理学院五、单件车间排序(páixù)问题（n/m/G/Fmax）能动作业计划的构成步骤：①设t＝1，{St}为空，{Ot}为各工件第一道工序的集合。②求最小的最早完工时间T*=min{T’k},并找到出现(chūxiàn)T*的机器M*，若有多台，任选一台。③从{Ot}中跳出满足以下两条件的工序Oj需要机器M*加工；Tj<T*④将确定的Oj放入{St}，从{Ot}中消去Oj并将Oj的紧后工序放入{Ot}中，使t=t+1。⑤若还有未安排的工序，转步骤②；否则，停止。第二十九页，共38页。华中科技大学管理学院一个(yīɡè)实例：D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345i1{Ot}TkT’kT*M*Oj1,1,1022M11,1,12,1,30321,2,3263M32,1,32,1,30331,2,3377M31,2,32,2,13741,3,2787M12,2,12,2,13751,3,2788M21,3,22,3,2712613M22,3,22,3,2813第三十页，共38页。华中科技大学管理学院得到加工顺序(shùnxù)矩阵：S=1,1,12,2,11,3,22,3,22,1,31,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M323773813第三十一页，共38页。华中科技大学管理学院五、单件车间排序(páixù)问题（n/m/G/Fmax）3、无延迟作业计划的构成没有任何延迟出现的能动作业计划。所谓“延迟”，指有工件等待加工时，机器出现空闲，即使这段空闲时间不足以完成一道(yīdào)工序。构成步骤：第三十二页，共38页。华中科技大学管理学院五、单件车间(chējiān)排序问题（n/m/G/Fmax）无延迟作业计划的构成步骤：①设t＝1，{St}为空，{Ot}为各工件第一道工序的集合(jíhé)。②求最小的最早完工时间T*=min{Tk},并找到出现T*的机器M*，若有多台，任选一台。③从{Ot}中跳出满足以下两条件的工序Oj需要机器M*加工；Tj=T*④将确定的Oj放入{St}，从{Ot}中消去Oj并将Oj的紧后工序放入{Ot}中，使t=t+1。⑤若还有未安排的工序，转步骤②；否则，停止。第三十三页，共38页。华中科技大学管理学院一个(yīɡè)实例：D=1,1,11,2,31,3,22,1,32,2,12,3,2T=241345i1{Ot}TkT’kT*M*Oj1,1,1020M11,1,12,1,30321,2,3260M32,1,32,1,30331,2,3373M31,2,32,2,13741,3,2783M12,2,12,2,13751,3,2787M22,3,22,3,2712612M21,3,22,3,212130M33M17M2第三十四页，共38页。华中科技大学管理学院得到加工顺序(shùnxù)矩阵：S=1,1,12,2,12,3,21,3,22,1,31,2,31,1,12,1,31,2,32,2,11,3,22,3,2M1M2M3237731213第三十五页，共38页。华中科技大学管理学院4、启发式算法：能动作业计划和无延迟作业计划尽管不一定是最优作业计划，但一般是较好的作业计划，特别是无延迟作业计划能提供令人满意的解。一般能动作业计划和无延迟作业计划都有多个，可用启发式方法从中选择结果较好的作业计划。一般来说，以构成(gòuchéng)无延迟作业计划的步骤为基础的启发式算法比以构成(gòuchéng)能动作业计划的步骤为基础的启发算法的效果要好。五、单件车间(chējiān)排序问题（n/m/G/Fmax）第三十六页，共38页。华中科技大学管理学院优选调度法则：SPT(ShortestProcessingTime)法则：优先选择加工时间最短的工序。FCFS(FirstComeFirstServed)法则：优先选择最早进入可排工序集合的工件(gōngjiàn)。EDD(EarliestDueDate)法则：优先选择完工期限紧的工件(gōngjiàn)。MWKR(MostWorkRemaining)法则：优先选择余下加工时间最长的工件(gōngjiàn)。LWKR(LeastWorkRemaining)法则：优先选择余下加工时间最短的工件(gōngjiàn)。MOPNR(MostOperationsRemaining)法则：优先选择余下工序数最多的工件(gōngjiàn)。五、单件车间排序(páixù)问题（n/m/G/Fmax）第三十七页，共38页。华中科技大学管理学院优选调度法则：按SPT法则可使工件的平均流程时间最短，从而减少在制品量。FCFS法则来自排队论，它对工件较公平。EDD法则可使工件最大延误时间最小。SCR也是保证工件延误最少的法则。MWKR法则使不同工作量的工件的完工时间尽量接近。LWKR法则，使工作量小的工件尽快完成(wánchéng)。MOPNR法则与MWKR法则类似，只不过考虑工件在不同机器上的转运排队时间是主要的。五、单件车间排序(páixù)问题（n/m/G/Fmax）第三十八页，共38页。华中科技大学管理学院