基于供应链的多目标平行机生产调度以及多属性决策分析硕士学位论文.doc

《基于供应链的多目标平行机生产调度以及多属性决策分析硕士学位论文.doc》由会员分享，可在线阅读，更多相关《基于供应链的多目标平行机生产调度以及多属性决策分析硕士学位论文.doc（65页珍藏版）》请在三一办公上搜索。

1、基于供应链的多目标平行机生产调度以及多属性决策分析Multi-objective Parallel Machine Scheduling in Supply Chain and Multiple Attribute Decision Making 独 创 性 声 明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 合肥工业大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签字：

2、山银华 签字日期： 年 月 日学位论文版权使用授权书 本学位论文作者完全了解 合肥工业大学 有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权 合肥工业大学 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）学位论文者签名： 山银华 导师签名： 签字日期： 2011 年 4 月29 日 签字日期： 年 月 日学位论文作者毕业后去向：工作单位： 电话：通讯地址： 邮编：毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所

3、呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它

4、复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本

5、学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日指导教师评阅书指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神 优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力 优 良 中 及格 不及格4、研究方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文（设计）期间的出勤情况 优 良 中 及格 不及格二、

6、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）指导教师： （签名） 单位： （盖章）年 月 日评阅教师评阅书评阅教师评价：一、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？

7、优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格二、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）评阅教师： （签名） 单位： （盖章）年 月 日教研室（或答辩小组）及教学系意见教研室（或答辩小组）评价：一、答辩过程1、毕业论文（设计）的基本要点和见解的叙述情况 优 良 中 及格 不及格2、对答辩问题

8、的反应、理解、表达情况 优 良 中 及格 不及格3、学生答辩过程中的精神状态 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格评定成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）教研室主任（或答辩小组组长）： （签

9、名）年 月 日教学系意见：系主任： （签名）年 月 日基于供应链的多目标平行机生产调度以及多属性决策分析摘 要在竞争日益激烈的市场经济环境下，供应链环境下的整体优化已经成为热点研究方向。本文在这个大背景下，提出了基于供应链的多目标平行机生产调度模型，使用多目标遗传算法求得Pareto最优解集，最后采用多属性决策的方法对解集对应的方案进行决策，选择符合实际情况的方案。本文的主要工作如下：1、研究了供应链环境下车间调度的背景，国内外研究现状和发展趋势，并对本文课题的研究意义进行了叙述。2、对供应链环境，平行机车间调度，多目标优化等问题进行介绍，并结合三者提出了新型的基于供应链环境的多目标平行机生产

10、调度模型。3、对主流的解决多目标优化问题的各种算法进行研究，并采用非支配排序算法NSGA-对本文的模型进行求解，进行仿真实验。4、以往的大量研究，在求得多目标优化问题的Pareto最优解集之后就结束了，本文通过多属性决策的方法，对Pareto最优解集进行决策，选择最符合当前供应链环境的解。关键字：供应链；平行机调度；多目标；NSGA-；多属性决策Multi-objective Parallel Machine Scheduling in Supply Chain and Multiple Attribute Decision MakingABSTRACTIn an increasingly c

11、ompetitive market economy environment,the whole optimization under the supply chain environment has become a hot research direction. Based on the background,the proposed multi-objective parallel machine scheduling model based on supply chain,obtain the Pareto optimal solution set with multi-objectiv

12、e genetic algorithm.Then by multi-attribute decision-making method, choose the scheme tally with the actual situation.This main job in this paper:1.Study the scheduling problem under supply chain environment, research current situation and development trend, and narrative research significance.2.Exp

13、ound the supply chain environment, parallel machine scheduling, and the multi-objective optimization problems, and by combining with three propose new multi-objective parallel machine scheduling model based on SCM environment.3. Research all kinds of algorithm that solve multi-objective optimization

14、 problems,solve the model by NSGA-, and simulation experiment.4.The past extensive research is finished after giving multi-objective optimization problems Pareto optimal solution set.This paper through multiple attribute decision making method,choose the most accord with current SCM environment solu

15、tion from Pareto optimal solution set.Key word: supply chain; Parallel machine scheduling; multi-objective；The NSGA ; - Multiple attribute decision making.致 谢本论文是在导师刘林副教授的悉心指导下完成的。回首近三年的研究生生活，我所取得的每一点进步和成绩都离不开导师的关心和帮助。导师渊博的学识、严谨求实的治学态度和兢兢业业的工作精神时时影响着我，使我受益匪浅。在此，谨向导师致以衷心的感谢和诚挚的敬意!另外，在整个硕士期间，教研室的刘心报老师

16、、程浩老师、裴凤老师、周谧老师在我的学习中也给了我多方面的支持和帮助，在此也向他们表示诚挚的感谢!在本论文的写作中还要感谢管理学院决策所的所有同学，在我的论文写作过程中，他们对我帮助很多，同时在生活中也给予我很多支持和关心。同时也向我的家人表示最深情的感谢！ 作者： 山银华 2011年 4 月 20 日目录第一章绪论11.1 供应链环境下生产调度研究现状11.2 供应链环境下生产调度研究的意义21.3 本论文的主要工作2第二章 供应链下平行机多目标调度问题42.1 供应链环境简介42.1.1 供应链的概念42.1.2 供应链协同42.1.3 第三方物流的基本概念以及发展42.2 平行机车间调度

17、问题概述52.2.1 车间调度问题简介62.2.2 车间调度问题的特点62.2.3 平行机的调度问题简介72.3 多目标优化问题的基本概念72.4 供应链环境下并行机生产调度模型82.4.1 模型的变量描述82.4.2 数学模型92.5 本章小节10第三章 多目标调度问题的求解113.1 多目标优化算法简介113.1.1 传统多目标优化算法简介113.1.2 调度规则、组合规则与启发式算法113.1.3 多目标智能算法123.1.4 Pareto解集的概念133.2 多目标遗传算法简介143.2.1 遗传算法简介143.2.2 多目标遗传算法介绍163.2.3 几种常见的多目标遗传算法简介17

18、3.3 本章小结19第四章 非支配排序算法NSGA-介绍和使用204.1 小生境、精英策略和二元联赛选择204.1.1 小生境204.1.2 精英策略204.1.3 二元联赛选择204.2非支配排序算法（NSGA-）简介204.3非支配排序算法NSGA-的应用214.3.1 编码解码224.3.2 生成初始种群234.3.3 适应度函数的设定234.3.4 非劣前沿分级244.3.5 小生境技术254.3.6 精英策略254.3.7 NSGA-算法选择，交叉和变异算子的确定254.3.8 终止的遗传代数274.4 仿真实验274.5 本章小结28第五章 供应链下多目标模型的多属性决策295.1

19、 多属性决策的指标体系的建立295.1.1 多属性指标体系的简单介绍295.1.2 指标体系的标准化305.1.3 决策指标权重的确定325.1.4 多指标决策方法345.2 采用理想解法对Pareto解集进行决策355.2.1 理想解法（TOPSIS法）355.2.2 理想解法的应用385.3 本章小结41第六章 结束语426.1 总结426.2 展望42参考文献44插图清单图4. 1多目标遗传算法流程图22图5. 1解的分布36图5. 2调度方案3的甘特图40第一章 绪论当今市场环境下，竞争日益激烈，个性化以及及时性的客户需求使得制造业的生产方式已经从大批量、小品种向小批量、多品种的方向发

20、展，这使得制造业的生产调度问题的研究能够进行的更加深入和广泛。经过研究也表明，现在大多数的研究仅局限在企业内部，强调的是本企业的内部利益最大化，而不是协调整个供应链的整体效益，这样做的后果就是整个供应链的巨大的成本的付出，从而削弱整个供应链的竞争力，这与现在经济全球化的市场大环境是违背的。1.1 供应链环境下生产调度研究现状目前国内外关于供应链生产模式的研究主要集中在供应链调度的计划层面上，而对于实际操作的研究起步很晚。在供应链下生产调度管理机制、供应链下生产调度的信息通讯交流机制、供应链下上下流工序节点的利益分配机制上，学术界的研究最多。单一企业或部门的生产调度已经是学术界研究很深入的一个领

21、域，而随着市场经济全球化的竞争加剧，供应链管理的概念被引入，但是对于此的调度级问题尚比较欠缺。归结原因主要有三点：第一，供应链环境给调度问题带来了更多的不确定因素，动态性很明显；第二，子问题的规模过大，比如多个企业的协同生产调度问题，生产与运输的协同问题，生产调度与库存的协同问题等等；第三、供应链环境下的生产调度涉及的因素更多，约束条件也更多。1996年Rowe等人首次提出物流排序的概念1，成功将排序论引入供应链管理领域。之后，2003年Hall和Potts又发表了第一篇关于供应链排序（supply chain scheduling）的论文2。2004年，Hall 做了题为“supply ch

22、ain scheduling”的报告，介绍了有关供应链排序进一步研究的研究成果3-4。随后，有关供应链排序的研究逐步展开。供应链排序以生产费用和运输费用的总和最小为优化目标，集成研究生产调度与分批发送的协同优化问题。该问题分为考虑供应商生产、发送到制造商的供应商问题，考虑制造商生产、发送到分销商或者客户的制造商问题以及供应商与制造商的联合问题。目前，此领域的研究还不多，文5 （Zegordi，Kamal Abadi，Beheshti Nia）研究的是供应链下两阶段的调度问题，文章将供应链下的生产调度分为生产和运输两个阶段，第一阶段由若干个生产速度不同的供应商组成，第二阶段为若干个速度与运载能力

23、都不同的运输单位组成，作者将该问题作为混合整数规划问题构建了数学模型，并提出了一种新的遗传算法对其求解。文6和文7同样考虑了生产和运输两个阶段，但是模型和算法都有差异。文8( 柏孟卓,唐国春)进一步研究了考虑交货期约束的供应链排序问题，并将最大延迟和误工工件数纳入考虑。文9（宫华，陈大亨）针对供应链排序问题，提出了一种新的启发式算法。文10( 马飞,吴梦娜,孙宝凤等)研究大规模的供应链调度问题，提出了解决此类问题的一种非线性规划新算法。文11（吴学静,周泓,梁春华）研究带软时间窗的分批发送问题及其对需求分配与生产调度的影响，提出了一种协同进化粒子群优化算法。基于供应链环境，还有很多类似的文章都

24、在供应链环境下的生产调度问题上进行研究。除了生产与运输协同优化外，供应链环境下还有很多领域需要迫切的研究，如考虑生产与库存协同、生产与库存与运输三者协同、多时间阶段联合优化等等的问题。本文将着重对生产与库存与运输协同优化的问题进行深入研究。1.2 供应链环境下生产调度研究的意义基于供应链的生产调度具有与传统生产调度模式完全不同的特点，主要有：1、供应链下生产调度的优化空间更大，涉及的部门、组织更加的多，更加的复杂。他不仅要考虑本企业的各个职能部门，包括车间、仓库、运输、管理等等。目前多品种、小批量的生产模式要求企业的优化更加合理，以达到利益的最大化。2、供应链下生产调度，顾名思义，他更注重供应

25、链网络中相关节点的利益平衡，往往和原材料供应，运输，库存，产品销售等领域密切相关。与传统生产调度完工时间最短、最小化拖期、提高机器利用率等的目标不同，取而代之的是跨越整个供应链的优化目标。例如，整个供应链的最小拖期，库存最小化，价值最大化，最小生产时间等等。3、传统的车间调度更像是个科学问题，机械，数学，计算机方法运用特别多，而管理的特色不够突出。而供应链的生产调度问题需要其中各个节点的有效交流和协调，管理人员在整个供应链系统中将扮演至关重要的角色，他们将是保证整个供应链优化的基石。结合以上特点，本文将以供应链整体的优化为目标，希望拓宽供应链生产管理方法的研究与应用，改进现有制造业的生产模式，

26、推动供应链生产管理模式的创新。并希望有一定的实际意义。1.3 本论文的主要工作（1）本文首先介绍供应链环境的基本概念，接着对调度问题和多目标优化问题进行简单介绍，整合供应链，多目标优化问题，调度问题，提出新型的基于供应链的平行机多目标调度模型。（2）之后对于多目标优化算法进行阐述，介绍当今解决多目标优化问题比较流行的各种优化算法。并着重介绍多目标遗传算法，并使用多目标遗传算法来解决上章节中提出的基于供应链的平行机多目标调度模型。（3）对于求得的多目标pareto解集，采用管理决策的办法进行选择，以期协调供应链中上下流节点的利益平衡，从而达到双方满意的解集，并且供应链的整体效益也达到一定的效果。

27、章节安排如下：第一章：绪论，主要介绍了供应链环境下多目标调度的研究现状和研究意义。第二章：先介绍了供应链相关内容以及平行机排序问题的大概内容，接着简单介绍多目标优化问题的概念，提出了供应链环境下平行机多目标优化问题的模型。第三章：介绍主流的多目标优化算法，着重介绍多目标遗传算法，并且选取多目标遗传算法来求pareto最优解。第四章：选择非支配排序算法（NSGA-），对供应链下平行机多目标优化问题进行求解。第五章：采集供应链上下流协调信息，对pareto最优解进行决策，利用AHP方法得到指标权重，然后采用TOPSIS法决策选择符合各方利益和供应链整体优化的最优的解。最后给出总结，提出创新点，不足

28、和今后研究工作的方向。第二章 供应链下平行机多目标调度问题2.1 供应链环境简介本文将考虑供应链环境下的车间调度问题，因此首先对供应链这个环境要有认识。 2.1.1 供应链的概念美国供应链协会将供应链管理定义为：“encompasses every effort involved in production and delivering a final product from the suppliers supplier to customers customer.”即供应链管理包括从供应商的供应商开始到客户的客户结束，所有涉及到产品生产和递送的活动。以上定义，概括了供应链管理的范围以及基本

29、流程，从源头的供应商到源尾的客户，基本活动包括了产品计划、采购、制造、配送四个环节。一条简单的供应链中，首先执行原材料的采购，经过中间制造商的加工成为成品，然后或者经过第三方物流商，或者直接交给用户，完成供应链的整个活动。其中供应商，生产商，物流商，客户可以是一到多家的企业，形成整个供应链网络。在整个供应链中，要围绕核心企业来展开活动，但是也要兼顾其他企业的利益，这样才能保证整个供应链的优化。当今世界市场经济的日益全球化，供应链活动小到地区，大到整个全球，这些供应链中节点的活动将影响到整个供应链的整体效益，对供应链中商流、物流、资金流、信息流的控制至关重要。2.1.2 供应链协同供应链协同（S

30、upply Chain Coordination，SCC）是在20世纪90年代中期所提出来的一个概念。他的概念是13：供应链中各个节点为了提高整个供应链的竞争力而进行彼此的协调和相互努力。各个节点上的企业为了整个供应链的利益，通过协商，联合形成一个联合体，相互交换信息，紧密合作，提高整个供应链的市场竞争力。英国著名供应链管理专家马力克里斯托夫说：“世纪的竞争不是企业与企业之间的竞争，而是供应链与供应链之间的竞争”。供应链协同是供应链管理的基础，协同要求供应链上的合作伙伴共享物流、信息流，供应链之间的竞争是供应链协同的动力，在日益激烈的全球化竞争中，要想生存，要想发展，供应链协同的群体竞争思想的

31、理解和竞争观念的创新，将成为新一轮市场经济的竞争优势。供应链内部的矛盾重重，解决这个矛盾将是发展的契机。2.1.3 第三方物流的基本概念以及发展第三方物流（The Third party Logistics，简称3PL或TPL），是指生产企业为集中主要力量搞好主营业务，把原来属于自己的物流活动，以合同方式委托给专业物流服务企业，因此第三方物流又叫合同制物流，以达到对物流全程的管理和控制的一种物流运作与管理方式，同时通过信息系统与物流服务企业保持密切联系。2009年，随着宏观经济企稳回升势头逐步增强，特别是物流业调整和振兴规划的出台，极大地提振了行业信心，我国物流业运行总体呈现回升向好的发展态势

32、。大力发展以第三方物流为特征的现代物流服务既是推动我国经济质量升级的一条重要渠道，也是我国传统运输物流企业转型的必然要求。自第三方物流伴随现代物流理念传入我国以来，已经有了长足发展，并呈现出较为明显的特征。在欧美等发达国家，第三方物流业一般处于产品生命周期的成长期。根据2009年不完全统计，国内大约有1.8万家已注册第三方物流企业，其中90%是小型私营企业，市场占领速度以及整合速度受限，尚处于初期阶段。2010年以来，我国经济总体形势良好，物流运行在2009年企稳回升的基础上，重回快速发展通道。2009年我国社会物流总额同比增长6%左右，物流业增加值同比增长约8%。2010年1-11月，社会物

33、流总额为114.6万亿元，按可比价格计算，同比增长16.2%。现代物流作为国家重点发展的战略性产业得到了社会各界的广泛关注与支持，第三方物流发展进一步加快了进程，在服务内涵、经营模式、功能建设等方面发生了深远的变革，呈现出良好发展趋势，服务链不断延伸、专业化不断加强。外资对国内第三方物流企业并购明显升温，进一步加快了中国第三方物流企业的全球化进程，也使第三方物流企业竞争从服务竞争扩展到资本竞争，这也是一个显著的特征。资本手段越来越成为物流企业做强做大的重要途径。在全球经济一体化影响下，中国正在成为第三方物流发展最迅速的国家之一。我国第三方物流处于发展初期，而且呈地域性集中分布，未来市场潜力很大

34、。推动中国第三方物流发展的主要因素，首先在于跨国企业正在将更多的业务转向中国，并通过外包他们广泛的物流功能来降低供应链成本；其次是中国公司面临着降低成本而增加了物流外包的需求；最后是政府的激励措施也是刺激中国第三方物流市场迅速发展的重要因素。 本文以此为背景，第三方物流公司和制造业同时管理库存的模型进行研究，假设供应链下流只有一个目的地的物流公司承担。2.2 平行机车间调度问题概述从1954年，S.M.Johnson发表的关于两台机器、同顺序的一个简单问题的文章开始，排序也即调度问题，发展日新月异。近几十年来，在运筹学，管理学，计算机学，工程管理学等等学科的研究中，调度问题都极具生命力和研究价

35、值，这也是因为这会给企业带来巨大的经济效益。2.2.1 车间调度问题简介企业的调度问题是指在实施时间内利用有限的资源更优化的达到某一个目的的过程。调度问题的产生就在于，企业资源有限，无法同时满足所有任务的需求，这就需要对资源进行合理的分配，以希望在某些指标上达到所需要的理想点。本文研究的是车间调度问题，空间和时间上存在某种约束，而要求某些目标达到最优化效果，例如最小完工时间、最小拖期惩罚、最小费用等等，车间调度问题一般属于NP难问题，他要满足非常复杂的约束条件，来进行组合优化。2.2.2 车间调度问题的特点在实际生产中，车间调度问题会面临很复杂的情况，比如订单的动态产生，机器加工故障，人为的随

36、机控制等等，这都是我们所要解决的问题。所以车间调度有以下的几个特点14：（1）复杂性车间调度问题一般都属于NP难的复杂问题，其原因主要有：生产因素的复杂性，工件、机器、工人等都是相互影响的个体，有其要考虑的非常众多的因素，比如工件要考虑他的加工时间，交货时间，库存大小等因素，而机器要考虑加工能力，维护，故障等因素，如果再加入动态调度，那问题将更加复杂；调度问题的复杂性，随着他的发展，已经从单目标向多目标转换，而每多一个目标，其计算量就有可能是指数级别的增长，常规的方法即使能取得最优解，计算时间也是我们所不可估量的。（2）动态性生产过程中，有很多随机的突发的因素，比如有不可延迟的急需订单到达（包

37、括军需、应急物资等）、机器的故障和修理、工人操作失误等等，都需要我们对调度方案进行调整，这也从一方面增加了调度问题的复杂性。（3）多目标单目标的调度问题已经不适合现在的实际调度问题了，传统的加工时间最小化问题往往是要牺牲其他一些利益的，比如超过交货期而影响企业业务，过早生产产生库存费用，赶时间导致生产成本增加，机器生产能力不同导致机器空闲浪费资源等等。目前基于多目标优化的调度问题层出不穷，不仅要求完工时间小，经常设计的目标问题还包括：最小拖期惩罚，最小生产费用，最大化设备利用率等，虽然这些目标会存在冲突，但是对于现如今的调度问题不可避免。（4）多约束这是调度问题产生的很大一个动力，正是因为生产

38、过程中存在大量的约束，调度问题才有实际意义。一般调度问题考虑的因素包括：机器的生产能力，缓存（可以考虑为库存）的大小约束，工件的加工顺序，运输工具的能力约束，订单的交货约束等。2.2.3 平行机的调度问题简介 最经典的调度问题可以描述为：有m（，）台机器和n（，）个工件，每个工件对应的加工时间t（，）。机器和工件随时都可以加工，但是每个工件只可以在一个机器上加工，而且中间不能够停止，目标就是最小化完工时间。机器通常可以分为两大类：平行机和串联机。由以上经典问题的模型可知，一个工件只需要在m台机器中的任何一台上加工，不间断一次就可以完成任务。但是如果在串联机上加工，则必须在每台机器上都加工一次才

39、可以完成任务。 目前平行机的种类主要有以下几种： 同型平行机（identical parallel machines），即所有的机器加工速度一样。 同类平行机（uniform parallel machines），即机器虽然有不同的加工速度，但是各个机器的加工速度之间有着相同的比例关系。 不同类平行机（unrelated parallel machines），即机器的加工速度既不一样，各个机器的加工速度之间也没有比例关系。 串联机也可以分为三类： 流水作业（flow shop），即每个工件都要以各自特定的同样的顺序在机器上加工。 自由作业（open shop），即工件的加工次序可以任意。 异序

40、作业（job shop），即每个工件以各自特定的顺序在机器上加工。 本文结合文6提出的单目标生产调度模型和文15提出的模型上再进行改进，提出在供应链环境下的同型平行机的多目标生产调度模型。2.3 多目标优化问题的基本概念从多目标优化问题的出现到现在，他的发展迅速，成为了最优化问题的一个重要分支。简单的说就是在约束条件下，多个数值目标同时优化的问题。以在一组约束条件下，最小化多目标问题为例，多目标优化问题（Multi-objective Optimization Problem ，MOP）可以描述为下面的形式12：式中：为带有p个决策变量的向量，组成决策空间；为带有m个目标函数的向量，组成目标空

41、间；为n个不等式约束函数，由它们形成了可行解区域。在1896年，经济学家V.Pareto在他的经济平衡的研究中首先提出了多目标的最优化问题，也第一次出现了pareto最优的概念12。从此，学者们便逐步开始了对多目标优化问题的研究。从20世纪50年代开始，多目标优化方法层出不穷，Kulm，Arrow，Karlin，Chame，Polak，Kceney，Klingcr和Geoffrion等都做出了相应的贡献，出现了加权和法、目标规范法、-约束法等基于权重的多目标优化算法。2.4 供应链环境下并行机生产调度模型2.4.1 模型的变量描述 假设制造商H有m台平行机机器，为，n个工件，为，可以记为N1，

42、2，n，每一个工件都有不同的加工时间，可以记为T，每一个工件完成后都会在制造企业产生一个库存量，记为S，在制造商就会产生一个库存费用，直到工件被运走，制造商的库存能力有限，上限为。而在下游有一个第三方物流商，从制造商将工件运至到交给最后的客户，也会有一个库存费用。车辆的运输能力有限，设为a，从制造商到达物流商的时间为常数。用表示工件n在机器m上的开工时刻，表示工件n在机器m上的完工时刻，将时刻从小到大顺序依次赋给，i1，2，n。表示时刻制造商的库存量。表2.1表示了问题中的一些参数。表2.1 数学符号表表示工件n的加工时间表示工件n到达物流商的时间表示工件n的库存量取1表示工件n在机器m上加工取0表示工件n不在机器m上加工车辆从制造商到物流商的运输时间，可以认为是常数表示工件n在机器m上的开工时刻表示工件n在机器m上的完工时刻w第一件工件开始加工到最后一批工件运送至下流物流商然后车辆返回制造商的总时间表示制造商工件