具有学习效应的总完工时间流水线排序问题与仿真答辩稿

具有学习效应的总完工时间流水线排序与仿真 导师： 班级： 学号： 姓名： （一） 排序问题 排序问题的定义： 排序 (scheduling)问题是一类重要的组合最优化问题，它是利用一些处理机 (processor)、机器(machine)或资源 ( resource )，最优地完成一批给定的任务 (task)或作业 (job)。 第一章 绪论 （二） 排序问题的分类 1.根据处理机的数量 处理机只有一个处理机的排序问题称为单 (处理 )机 (single processor, single machine)排序问题，否则称为多 (处理 )机排序问题。 2.根据处理机的功能 如果所有的处理机都具有相同的功能，称它们为同类机或平行机。同类机亦有同速机、恒速机、变速机之分。 3.根据加工顺序的特征 （ 1） 如果每个作业需要在每个处理机上加工，而且每个作业的工序也相同，这种多类机的环境称为同顺序作业或流水作业 (flow shop)。 （ 2） 如果每个作业需要在每个处理机上加工，每个作业有自己的加工顺序，称之为异顺序作业 (job shop) （ 3）如果每个作业需要在每个处理机上加工，每个作业可按任意顺序加工，把它称为自由顺序作业或开放作业 (open shop ) 。 (4)柔性流水线 例 1.1 给定排序问题 1| | 其中 n=4, P=(3，2， 5， i)， r=(0， 1， 0， 0) ， ， ， 是一个可行排序，对应的总加工时间是 31, ， ， ， 是一个最优排序，最优总加工时间是 21。 jr jC1P34P24P2P1P3符号说明 第二章 具有学习效应的总完工时间流水线排序 2.1 问题描述 2.2学习效应的概念 2.3 单机排序问题 2.4数学规划模型 2.5 启发式算法 2.6 数值试验 2.1 问题描述 n个工件依次在机器 M1、 M2上加工。在每个机器上的加工顺序相同 ,其实际加工时间为 ，公式可表示为： 对于 2台机器上具有指数学习效应的最大完工时间的流水作业问题 ,用三参数表示法表示为 ijP2.学习效应 学习曲线方程的一般形式是 : Yx=K（ n为 X的指数） 式中 : X =单位数量 = 生产第 X个产品所需的直接劳动小时数 K = 生产第一个产品所需的直接劳动小时数 n = lgb/lg X，其中 b 为学习比例 2.4 数学规划模型 2.6 数值试验 1. 基本假设 （ 1）工件数为 5个，机器数为 2台 （ 2）假设第 1台机器上第 r个工件的完工时间和它在第2台机器上的开始时间之差皆为 5min。 （ 3）假设 5个不同工件在第一台机器每一个批次的实际加工时间分别为 4,6,7,5,9。在第二台机器实际加工时间分别为 7,11,10,9,6。另外，每种工件各有 5个批次。 （ 4）假设学习因子 =0.9 （ 5）假设第二台机器上第 r个工件的开始时间与第 r-1个工件的完工时间之间的空闲时间为 0 第三章 流水线作业排序模型仿真 SPT算法规则 最短作业时间法则 (SPT) ：最小化平均流程时间。 job作业时间越小者排越前面，亦可以使平均延误时间，平均等候时间最小化。 致 谢 : 经过几周的奋战我的毕业设计终于完成了。在我还没有做毕业设计以前觉得毕业设计只是对这几年来所学知识的单纯性的总结，但是通过这次做毕业设计发现自己的看法有点太片面和简单了。通过这次毕业设计使我明白了自己原来的知识还是比较欠缺。自己要学习的东西还太多太多，以前总是觉得自己什么东西都会，什么东西都懂，有点眼高手低。通过这次毕业设计的收集编制等等，我才明白学习是一个长期积累的过程，在以后的工作和生活当中我们都应该不断的努力学习，努力的去提高自己