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

基于供应链的多目标平行机生产调度以及多属性决策分析Multi-objective Parallel Machine Scheduling in Supply Chain and Multiple Attribute Decision Making 独 创 性 声 明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得 合肥工业大学 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签字：山银华 签字日期： 年 月 日学位论文版权使用授权书 本学位论文作者完全了解 合肥工业大学 有关保留、使用学位论文的规定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权 合肥工业大学 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）学位论文者签名： 山银华 导师签名： 签字日期： 2011 年 4 月29 日 签字日期： 年 月 日学位论文作者毕业后去向：工作单位： 电话：通讯地址： 邮编：毕业设计（论文）原创性声明和使用授权说明原创性声明本人郑重承诺：所呈交的毕业设计（论文），是我个人在指导教师的指导下进行的研究工作及取得的成果。尽我所知，除文中特别加以标注和致谢的地方外，不包含其他人或组织已经发表或公布过的研究成果，也不包含我为获得 及其它教育机构的学位或学历而使用过的材料。对本研究提供过帮助和做出过贡献的个人或集体，均已在文中作了明确的说明并表示了谢意。作 者 签 名： 日 期： 指导教师签名： 日期： 使用授权说明本人完全了解 大学关于收集、保存、使用毕业设计（论文）的规定，即：按照学校要求提交毕业设计（论文）的印刷本和电子版本；学校有权保存毕业设计（论文）的印刷本和电子版，并提供目录检索与阅览服务；学校可以采用影印、缩印、数字化或其它复制手段保存论文；在不以赢利为目的前提下，学校可以公布论文的部分或全部内容。作者签名： 日 期： 学位论文原创性声明本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。作者签名： 日期： 年 月 日学位论文版权使用授权书本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权 大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。涉密论文按学校规定处理。作者签名：日期： 年 月 日导师签名： 日期： 年 月 日指导教师评阅书指导教师评价：一、撰写（设计）过程1、学生在论文（设计）过程中的治学态度、工作精神 优 良 中 及格 不及格2、学生掌握专业知识、技能的扎实程度 优 良 中 及格 不及格3、学生综合运用所学知识和专业技能分析和解决问题的能力 优 良 中 及格 不及格4、研究方法的科学性；技术线路的可行性；设计方案的合理性 优 良 中 及格 不及格5、完成毕业论文（设计）期间的出勤情况 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）指导教师： （签名） 单位： （盖章）年 月 日评阅教师评阅书评阅教师评价：一、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格二、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格建议成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）评阅教师： （签名） 单位： （盖章）年 月 日教研室（或答辩小组）及教学系意见教研室（或答辩小组）评价：一、答辩过程1、毕业论文（设计）的基本要点和见解的叙述情况 优 良 中 及格 不及格2、对答辩问题的反应、理解、表达情况 优 良 中 及格 不及格3、学生答辩过程中的精神状态 优 良 中 及格 不及格二、论文（设计）质量1、论文（设计）的整体结构是否符合撰写规范？ 优 良 中 及格 不及格2、是否完成指定的论文（设计）任务（包括装订及附件）？ 优 良 中 及格 不及格三、论文（设计）水平1、论文（设计）的理论意义或对解决实际问题的指导意义 优 良 中 及格 不及格2、论文的观念是否有新意？设计是否有创意？ 优 良 中 及格 不及格3、论文（设计说明书）所体现的整体水平 优 良 中 及格 不及格评定成绩： 优 良 中 及格 不及格（在所选等级前的内画“”）教研室主任（或答辩小组组长）： （签名）年 月 日教学系意见：系主任： （签名）年 月 日基于供应链的多目标平行机生产调度以及多属性决策分析摘 要在竞争日益激烈的市场经济环境下，供应链环境下的整体优化已经成为热点研究方向。本文在这个大背景下，提出了基于供应链的多目标平行机生产调度模型，使用多目标遗传算法求得Pareto最优解集，最后采用多属性决策的方法对解集对应的方案进行决策，选择符合实际情况的方案。本文的主要工作如下：1、研究了供应链环境下车间调度的背景，国内外研究现状和发展趋势，并对本文课题的研究意义进行了叙述。2、对供应链环境，平行机车间调度，多目标优化等问题进行介绍，并结合三者提出了新型的基于供应链环境的多目标平行机生产调度模型。3、对主流的解决多目标优化问题的各种算法进行研究，并采用非支配排序算法NSGA-对本文的模型进行求解，进行仿真实验。4、以往的大量研究，在求得多目标优化问题的Pareto最优解集之后就结束了，本文通过多属性决策的方法，对Pareto最优解集进行决策，选择最符合当前供应链环境的解。关键字：供应链；平行机调度；多目标；NSGA-；多属性决策Multi-objective Parallel Machine Scheduling in Supply Chain and Multiple Attribute Decision MakingABSTRACTIn an increasingly competitive 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-objective 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.Expound 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 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 solution from Pareto optimal solution set.Key word: supply chain; Parallel machine scheduling; multi-objective；The NSGA ; - Multiple attribute decision making.致 谢本论文是在导师刘林副教授的悉心指导下完成的。回首近三年的研究生生活，我所取得的每一点进步和成绩都离不开导师的关心和帮助。导师渊博的学识、严谨求实的治学态度和兢兢业业的工作精神时时影响着我，使我受益匪浅。在此，谨向导师致以衷心的感谢和诚挚的敬意!另外，在整个硕士期间，教研室的刘心报老师、程浩老师、裴凤老师、周谧老师在我的学习中也给了我多方面的支持和帮助，在此也向他们表示诚挚的感谢!在本论文的写作中还要感谢管理学院决策所的所有同学，在我的论文写作过程中，他们对我帮助很多，同时在生活中也给予我很多支持和关心。同时也向我的家人表示最深情的感谢！ 作者： 山银华 2011年 4 月 20 日目录第一章绪论11.1 供应链环境下生产调度研究现状11.2 供应链环境下生产调度研究的意义21.3 本论文的主要工作2第二章 供应链下平行机多目标调度问题42.1 供应链环境简介42.1.1 供应链的概念42.1.2 供应链协同42.1.3 第三方物流的基本概念以及发展42.2 平行机车间调度问题概述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 几种常见的多目标遗传算法简介173.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 多属性决策的指标体系的建立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第一章 绪论当今市场环境下，竞争日益激烈，个性化以及及时性的客户需求使得制造业的生产方式已经从大批量、小品种向小批量、多品种的方向发展，这使得制造业的生产调度问题的研究能够进行的更加深入和广泛。经过研究也表明，现在大多数的研究仅局限在企业内部，强调的是本企业的内部利益最大化，而不是协调整个供应链的整体效益，这样做的后果就是整个供应链的巨大的成本的付出，从而削弱整个供应链的竞争力，这与现在经济全球化的市场大环境是违背的。1.1 供应链环境下生产调度研究现状目前国内外关于供应链生产模式的研究主要集中在供应链调度的计划层面上，而对于实际操作的研究起步很晚。在供应链下生产调度管理机制、供应链下生产调度的信息通讯交流机制、供应链下上下流工序节点的利益分配机制上，学术界的研究最多。单一企业或部门的生产调度已经是学术界研究很深入的一个领域，而随着市场经济全球化的竞争加剧，供应链管理的概念被引入，但是对于此的调度级问题尚比较欠缺。归结原因主要有三点：第一，供应链环境给调度问题带来了更多的不确定因素，动态性很明显；第二，子问题的规模过大，比如多个企业的协同生产调度问题，生产与运输的协同问题，生产调度与库存的协同问题等等；第三、供应链环境下的生产调度涉及的因素更多，约束条件也更多。1996年Rowe等人首次提出物流排序的概念1，成功将排序论引入供应链管理领域。之后，2003年Hall和Potts又发表了第一篇关于供应链排序（supply chain scheduling）的论文2。2004年，Hall 做了题为“supply chain scheduling”的报告，介绍了有关供应链排序进一步研究的研究成果3-4。随后，有关供应链排序的研究逐步展开。供应链排序以生产费用和运输费用的总和最小为优化目标，集成研究生产调度与分批发送的协同优化问题。该问题分为考虑供应商生产、发送到制造商的供应商问题，考虑制造商生产、发送到分销商或者客户的制造商问题以及供应商与制造商的联合问题。目前，此领域的研究还不多，文5 （Zegordi，Kamal Abadi，Beheshti Nia）研究的是供应链下两阶段的调度问题，文章将供应链下的生产调度分为生产和运输两个阶段，第一阶段由若干个生产速度不同的供应商组成，第二阶段为若干个速度与运载能力都不同的运输单位组成，作者将该问题作为混合整数规划问题构建了数学模型，并提出了一种新的遗传算法对其求解。文6和文7同样考虑了生产和运输两个阶段，但是模型和算法都有差异。文8( 柏孟卓,唐国春)进一步研究了考虑交货期约束的供应链排序问题，并将最大延迟和误工工件数纳入考虑。文9（宫华，陈大亨）针对供应链排序问题，提出了一种新的启发式算法。文10( 马飞,吴梦娜,孙宝凤等)研究大规模的供应链调度问题，提出了解决此类问题的一种非线性规划新算法。文11（吴学静,周泓,梁春华）研究带软时间窗的分批发送问题及其对需求分配与生产调度的影响，提出了一种协同进化粒子群优化算法。基于供应链环境，还有很多类似的文章都在供应链环境下的生产调度问题上进行研究。除了生产与运输协同优化外，供应链环境下还有很多领域需要迫切的研究，如考虑生产与库存协同、生产与库存与运输三者协同、多时间阶段联合优化等等的问题。本文将着重对生产与库存与运输协同优化的问题进行深入研究。1.2 供应链环境下生产调度研究的意义基于供应链的生产调度具有与传统生产调度模式完全不同的特点，主要有：1、供应链下生产调度的优化空间更大，涉及的部门、组织更加的多，更加的复杂。他不仅要考虑本企业的各个职能部门，包括车间、仓库、运输、管理等等。目前多品种、小批量的生产模式要求企业的优化更加合理，以达到利益的最大化。2、供应链下生产调度，顾名思义，他更注重供应链网络中相关节点的利益平衡，往往和原材料供应，运输，库存，产品销售等领域密切相关。与传统生产调度完工时间最短、最小化拖期、提高机器利用率等的目标不同，取而代之的是跨越整个供应链的优化目标。例如，整个供应链的最小拖期，库存最小化，价值最大化，最小生产时间等等。3、传统的车间调度更像是个科学问题，机械，数学，计算机方法运用特别多，而管理的特色不够突出。而供应链的生产调度问题需要其中各个节点的有效交流和协调，管理人员在整个供应链系统中将扮演至关重要的角色，他们将是保证整个供应链优化的基石。结合以上特点，本文将以供应链整体的优化为目标，希望拓宽供应链生产管理方法的研究与应用，改进现有制造业的生产模式，推动供应链生产管理模式的创新。并希望有一定的实际意义。1.3 本论文的主要工作（1）本文首先介绍供应链环境的基本概念，接着对调度问题和多目标优化问题进行简单介绍，整合供应链，多目标优化问题，调度问题，提出新型的基于供应链的平行机多目标调度模型。（2）之后对于多目标优化算法进行阐述，介绍当今解决多目标优化问题比较流行的各种优化算法。并着重介绍多目标遗传算法，并使用多目标遗传算法来解决上章节中提出的基于供应链的平行机多目标调度模型。（3）对于求得的多目标pareto解集，采用管理决策的办法进行选择，以期协调供应链中上下流节点的利益平衡，从而达到双方满意的解集，并且供应链的整体效益也达到一定的效果。章节安排如下：第一章：绪论，主要介绍了供应链环境下多目标调度的研究现状和研究意义。第二章：先介绍了供应链相关内容以及平行机排序问题的大概内容，接着简单介绍多目标优化问题的概念，提出了供应链环境下平行机多目标优化问题的模型。第三章：介绍主流的多目标优化算法，着重介绍多目标遗传算法，并且选取多目标遗传算法来求pareto最优解。第四章：选择非支配排序算法（NSGA-），对供应链下平行机多目标优化问题进行求解。第五章：采集供应链上下流协调信息，对pareto最优解进行决策，利用AHP方法得到指标权重，然后采用TOPSIS法决策选择符合各方利益和供应链整体优化的最优的解。最后给出总结，提出创新点，不足和今后研究工作的方向。第二章 供应链下平行机多目标调度问题2.1 供应链环境简介本文将考虑供应链环境下的车间调度问题，因此首先对供应链这个环境要有认识。 2.1.1 供应链的概念美国供应链协会将供应链管理定义为：“encompasses every effort involved in production and delivering a final product from the suppliers supplier to customers customer.”即供应链管理包括从供应商的供应商开始到客户的客户结束，所有涉及到产品生产和递送的活动。以上定义，概括了供应链管理的范围以及基本流程，从源头的供应商到源尾的客户，基本活动包括了产品计划、采购、制造、配送四个环节。一条简单的供应链中，首先执行原材料的采购，经过中间制造商的加工成为成品，然后或者经过第三方物流商，或者直接交给用户，完成供应链的整个活动。其中供应商，生产商，物流商，客户可以是一到多家的企业，形成整个供应链网络。在整个供应链中，要围绕核心企业来展开活动，但是也要兼顾其他企业的利益，这样才能保证整个供应链的优化。当今世界市场经济的日益全球化，供应链活动小到地区，大到整个全球，这些供应链中节点的活动将影响到整个供应链的整体效益，对供应链中商流、物流、资金流、信息流的控制至关重要。2.1.2 供应链协同供应链协同（Supply Chain Coordination，SCC）是在20世纪90年代中期所提出来的一个概念。他的概念是13：供应链中各个节点为了提高整个供应链的竞争力而进行彼此的协调和相互努力。各个节点上的企业为了整个供应链的利益，通过协商，联合形成一个联合体，相互交换信息，紧密合作，提高整个供应链的市场竞争力。英国著名供应链管理专家马力克里斯托夫说：“世纪的竞争不是企业与企业之间的竞争，而是供应链与供应链之间的竞争”。供应链协同是供应链管理的基础，协同要求供应链上的合作伙伴共享物流、信息流，供应链之间的竞争是供应链协同的动力，在日益激烈的全球化竞争中，要想生存，要想发展，供应链协同的群体竞争思想的理解和竞争观念的创新，将成为新一轮市场经济的竞争优势。供应链内部的矛盾重重，解决这个矛盾将是发展的契机。2.1.3 第三方物流的基本概念以及发展第三方物流（The Third party Logistics，简称3PL或TPL），是指生产企业为集中主要力量搞好主营业务，把原来属于自己的物流活动，以合同方式委托给专业物流服务企业，因此第三方物流又叫合同制物流，以达到对物流全程的管理和控制的一种物流运作与管理方式，同时通过信息系统与物流服务企业保持密切联系。2009年，随着宏观经济企稳回升势头逐步增强，特别是物流业调整和振兴规划的出台，极大地提振了行业信心，我国物流业运行总体呈现回升向好的发展态势。大力发展以第三方物流为特征的现代物流服务既是推动我国经济质量升级的一条重要渠道，也是我国传统运输物流企业转型的必然要求。自第三方物流伴随现代物流理念传入我国以来，已经有了长足发展，并呈现出较为明显的特征。在欧美等发达国家，第三方物流业一般处于产品生命周期的成长期。根据2009年不完全统计，国内大约有1.8万家已注册第三方物流企业，其中90%是小型私营企业，市场占领速度以及整合速度受限，尚处于初期阶段。2010年以来，我国经济总体形势良好，物流运行在2009年企稳回升的基础上，重回快速发展通道。2009年我国社会物流总额同比增长6%左右，物流业增加值同比增长约8%。2010年1-11月，社会物流总额为114.6万亿元，按可比价格计算，同比增长16.2%。现代物流作为国家重点发展的战略性产业得到了社会各界的广泛关注与支持，第三方物流发展进一步加快了进程，在服务内涵、经营模式、功能建设等方面发生了深远的变革，呈现出良好发展趋势，服务链不断延伸、专业化不断加强。外资对国内第三方物流企业并购明显升温，进一步加快了中国第三方物流企业的全球化进程，也使第三方物流企业竞争从服务竞争扩展到资本竞争，这也是一个显著的特征。资本手段越来越成为物流企业做强做大的重要途径。在全球经济一体化影响下，中国正在成为第三方物流发展最迅速的国家之一。我国第三方物流处于发展初期，而且呈地域性集中分布，未来市场潜力很大。推动中国第三方物流发展的主要因素，首先在于跨国企业正在将更多的业务转向中国，并通过外包他们广泛的物流功能来降低供应链成本；其次是中国公司面临着降低成本而增加了物流外包的需求；最后是政府的激励措施也是刺激中国第三方物流市场迅速发展的重要因素。 本文以此为背景，第三方物流公司和制造业同时管理库存的模型进行研究，假设供应链下流只有一个目的地的物流公司承担。2.2 平行机车间调度问题概述从1954年，S.M.Johnson发表的关于两台机器、同顺序的一个简单问题的文章开始，排序也即调度问题，发展日新月异。近几十年来，在运筹学，管理学，计算机学，工程管理学等等学科的研究中，调度问题都极具生命力和研究价值，这也是因为这会给企业带来巨大的经济效益。2.2.1 车间调度问题简介企业的调度问题是指在实施时间内利用有限的资源更优化的达到某一个目的的过程。调度问题的产生就在于，企业资源有限，无法同时满足所有任务的需求，这就需要对资源进行合理的分配，以希望在某些指标上达到所需要的理想点。本文研究的是车间调度问题，空间和时间上存在某种约束，而要求某些目标达到最优化效果，例如最小完工时间、最小拖期惩罚、最小费用等等，车间调度问题一般属于NP难问题，他要满足非常复杂的约束条件，来进行组合优化。2.2.2 车间调度问题的特点在实际生产中，车间调度问题会面临很复杂的情况，比如订单的动态产生，机器加工故障，人为的随机控制等等，这都是我们所要解决的问题。所以车间调度有以下的几个特点14：（1）复杂性车间调度问题一般都属于NP难的复杂问题，其原因主要有：生产因素的复杂性，工件、机器、工人等都是相互影响的个体，有其要考虑的非常众多的因素，比如工件要考虑他的加工时间，交货时间，库存大小等因素，而机器要考虑加工能力，维护，故障等因素，如果再加入动态调度，那问题将更加复杂；调度问题的复杂性，随着他的发展，已经从单目标向多目标转换，而每多一个目标，其计算量就有可能是指数级别的增长，常规的方法即使能取得最优解，计算时间也是我们所不可估量的。（2）动态性生产过程中，有很多随机的突发的因素，比如有不可延迟的急需订单到达（包括军需、应急物资等）、机器的故障和修理、工人操作失误等等，都需要我们对调度方案进行调整，这也从一方面增加了调度问题的复杂性。（3）多目标单目标的调度问题已经不适合现在的实际调度问题了，传统的加工时间最小化问题往往是要牺牲其他一些利益的，比如超过交货期而影响企业业务，过早生产产生库存费用，赶时间导致生产成本增加，机器生产能力不同导致机器空闲浪费资源等等。目前基于多目标优化的调度问题层出不穷，不仅要求完工时间小，经常设计的目标问题还包括：最小拖期惩罚，最小生产费用，最大化设备利用率等，虽然这些目标会存在冲突，但是对于现如今的调度问题不可避免。（4）多约束这是调度问题产生的很大一个动力，正是因为生产过程中存在大量的约束，调度问题才有实际意义。一般调度问题考虑的因素包括：机器的生产能力，缓存（可以考虑为库存）的大小约束，工件的加工顺序，运输工具的能力约束，订单的交货约束等。2.2.3 平行机的调度问题简介 最经典的调度问题可以描述为：有m（，）台机器和n（，）个工件，每个工件对应的加工时间t（，）。机器和工件随时都可以加工，但是每个工件只可以在一个机器上加工，而且中间不能够停止，目标就是最小化完工时间。机器通常可以分为两大类：平行机和串联机。由以上经典问题的模型可知，一个工件只需要在m台机器中的任何一台上加工，不间断一次就可以完成任务。但是如果在串联机上加工，则必须在每台机器上都加工一次才可以完成任务。 目前平行机的种类主要有以下几种： 同型平行机（identical parallel machines），即所有的机器加工速度一样。 同类平行机（uniform parallel machines），即机器虽然有不同的加工速度，但是各个机器的加工速度之间有着相同的比例关系。 不同类平行机（unrelated parallel machines），即机器的加工速度既不一样，各个机器的加工速度之间也没有比例关系。 串联机也可以分为三类： 流水作业（flow shop），即每个工件都要以各自特定的同样的顺序在机器上加工。 自由作业（open shop），即工件的加工次序可以任意。 异序作业（job shop），即每个工件以各自特定的顺序在机器上加工。 本文结合文6提出的单目标生产调度模型和文15提出的模型上再进行改进，提出在供应链环境下的同型平行机的多目标生产调度模型。2.3 多目标优化问题的基本概念从多目标优化问题的出现到现在，他的发展迅速，成为了最优化问题的一个重要分支。简单的说就是在约束条件下，多个数值目标同时优化的问题。以在一组约束条件下，最小化多目标问题为例，多目标优化问题（Multi-objective Optimization Problem ，MOP）可以描述为下面的形式12：式中：为带有p个决策变量的向量，组成决策空间；为带有m个目标函数的向量，组成目标空间；为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，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第一件工件开始加工到最后一批工件运送至下流物流商然后车辆返回制造商的总时间表示制造商工件n的交货期表示物流商工件n的交货期2.4.2 数学模型 对于加工有如下的假设： （1）工件的加工时间是预知固定的。 （2）工件必须被连续加工，不允许中断。 （3）每台机器同一时间只能加工一个工件。 （4）在零时刻，每个工件都允许被加工。 （5）同一台机器上两个工件的加工，可以没有间隔，即便有间隔，也被 考虑到工件的加工时间之内。 （6）直到工件加工完才产生库存。 （7）库存能力有限。 （8）运输能力有限，必须在运输能力范围之内运输。 （9）假设每个工件的库存量肯定小于运输能力，在车辆返回制造商前， 物流商的库存要小于b。 （10）不同的工件虽然可以同一批次运输，但是同一批工件不能被分开运 输 根据模型的描述，建立以下数学模型： （2. 1） （2. 2） （2. 3） （2. 4） s.t. （2. 5） （2. 6） （2. 7） （2. 8） （2. 9） 其中表示制造商提前完工的惩罚系数（这个系数可以理解为制造商单位天数的库存费用），表示制造商延期交货的惩罚系数，表示物流商提前到货的惩罚系数（这个系数可以理解为物流商单位天数的库存费用），表示物流商延期交货的惩罚系数， 表示运输次数，当库存量超出上限时，要及时的运输，但是要保证在运输能力之内。 问题的目标函数2.1表示制造商从第一个工件制造开始到最后的工件运输完成的总时间最小，2.2表示制造商的拖期惩罚最小，2.3表示物流商的拖期惩罚最小，2.4表示运输运输次数最少。约束条件中，2.5至2.8表示工件在机器上是不间断的生产，而且同一时间，一个工件只能在一个机器上生产，一台机器只能生产一个工件。2.9表示制造商当前库存量不能超过上限。该类问题可以用五参数法21法表示： 式中表示生产阶段有多台平行机，且目的地只有一个，表示运输能力有限，上限为a，表示不同的订单产品可以在同一批次运送，表示目标函数。2.5 本章小节 本章首先介绍了供应链和供应链协同的相关概念，接着介绍了车间调度以及多目标优化的基本理论，并在其中着重介绍第三方物流和平行机调度概念，并且以此为背景来提出生产调度模型：基于供应链环境的多目标平行机生产调度模型。 第三章 多目标调度问题的求解3.1 多目标优化算法简介3.1.1 传统多目标优化算法简介很多传统的多目标优化算法没有太多的多目标概念，只是经过数学改良，又转换成了单目标优化算法，采用比较成熟的单目标优化算法来求解，比如，分层序列法，评价函数法，目标规划方法等等。传统多目标优化算法中有很多经典算法，比如：加权求和法：该方法就是将多目标问题中的各个目标函数增加权重，即在各个目标函数上再乘以权重系数，转化为单目标问题来求解。优点：这种方法将多目标问题转化为单目标问题，将问题简化，在Pareto最优前端为凸的问题中，可以确定得到Pareto最优解。缺点：关键是权重的选取，而且在搜索空间非凸时，很难求得Pareto最优解。-约束法：该方法是将目标中的某个目标作为优化目标，而将其他目标函数约束住来求解的优化方法。优点：该方法可以找到不同的Pareto最优解。缺点：约束选中目标外的其他目标的参数非常困难，有可能导致没有可行解或者其他目标的约束不起作用。等式约束法：该方法与-约束法类似，也是从多目标优化问题中选取其中一个目标函数进行优化，而约束其他目标函数。优点：只要选取合适的其他目标的约束参数，也可以获得不同的Pareto最优解。缺点：很多等式约束问题都不存在可行解，而且即使存在可行解，也不一定是Pareto最优解。最小最大法：这种方法起源于博弈论，是通过最小化各个目标函数值与预设的目标之间的最大偏移量来求得多目标最优解的方法，当初设计的初衷是为求解有冲突的目标函数。 3.1.2 调度规则、组合规则与启发式算法 （1）调度规则与组合规则 在传统的生产调度领域和组合优化领域存在大量成熟的调度规则或组合调度规则。基于现有的规则和实际生产环境中的经验知识，设计针对供应链环境生产调度问题的的调度规则或组合调度规则，同时分析各类规则的原理及其对系统性能的影响。这种方法一般求解效率较高、针对性强且有助于分析调度问题的本质和优化机理，也可用来构造智能算法的初始解，但它同时也存在设计难度大、扩展性低的缺点。（2）启发式算法 供应链下生产调度问题大多属于NP难问题，而由于制造业的生产调度问题规模一般比较庞大，所以设计启发式算法成为求解该类问题的主流。基于各种调度规则和实际生产环境的经验知识，设计供应链下生产调度问题的启发式算法，并在可以已知精确解的小规模问题中验证启发式算法的有效性，同时也可以将启发式算法的结果作为其它算法（比如多目标智能算法）的初始解。此种方法的优劣性质和规则相似。3.1.3 多目标智能算法供应链下的生产调度问题大多为约束类多目标问题，若想求解该类问题的Pareto解集，传统的多目标算法或启发式算法通常难以胜任，尤其对于问题规模较大的制造业来说。而基于Pareto解的多目标遗传算法和多目标粒子群算法已经被验证可以比较好的解决此类问题。（1）基于Pareto解的多目标遗传算法（进化算法）遗传算法（GeneticAlgorithms）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。遗传算法是解决搜索问题的一种通用算法，对于各种通用问题都可以使用。搜索算法的共同特征为：首先组成一组候选解（随机生成或由其它算法产生）；依据某些适应性条件测算这些候选解的适应度；根据适应度保留某些候选解，放弃其他候选解；对保留的候选解进行某些操作，生成新的候选解。在遗传算法中，上述几个特征以一种特殊的方式组合在一起：基于染色体群的并行搜索，带有猜测性质的选择操作、交换操作和变异操作。 其在解决多目标问题上也有良好的方法，即基于Pareto解的遗传算法，我们在保留子代的时候采用“支配解”的方式，在选择两个基因比较适应度的时候，若A完全优于B时，我们称A支配B，其中B为支配解，若A不被任何其他解（向量）支配，则称A为非支配解，我们通过遗传、交叉、变异等操作得到的一系列非支配解即为我们所需要的Pareto最优解集，其中最终的最优解我们让决策者根据自己的偏好程度来筛选。（2）多目标粒子群算法粒子群优化(Particle Swarm Optimization，PSO) 算法是近年来发展起来的一种新的进化算法。它和遗传算法相似,它也是从随机解出发,通过迭代寻找最优解,它也是通过适应度来评价解的品质，但是它比遗传算法规则更为简单,它没有遗传算法的“交叉”和“变异”操作。它通过追随当前搜索到的最优值来寻找全局最优。在PSO中，每个优化问题的解都是搜索空间中的一只鸟，（粒子群算法最初就是根据飞鸟觅食而得到的）我们称之为“粒子”。所有的粒子都有一个由被优化的函数决定的适应值(fitness value)，每个粒子还有一个速度决定他们飞翔的方向和距离，然后粒子们就追随当前的最优粒子在解空间中搜索。PSO 初始化为一群随机粒子(随机解)，然后通过迭代找到最优解。在每一次迭代中，粒子通过跟踪两个极值来更新自己。第一个就是粒子本身所找到的最优解，这个解叫做个体极值pBest，另一个极值是整个种群目前找到的最优解，这个极值是全局极值gBest。另外也可以不用整个种群而只是用其中一部分作为粒子的邻居，那么在所有邻居中的极值就是局部极值。在解决多目标问题时，我们将粒子的速度和位置用D唯向量来表示，所有粒子中，不劣于其他粒子的我们将其作为向之移动的目标，而劣解根据自己的位置和速度向着离自己最近的非劣解运动，从而得到一个Pareto最优解集，即解空间的边缘部分。求解单目标问题，粒子群算法有较快的收敛速度，但这可能使多目标的求解变得更糟，因为可能收敛到有偏差的非劣最优解集。本项目中我们采用变异算子等改进算法，使得Pareto解更广泛和均匀的覆盖到曲线边缘上。3.1.4 Pareto解集的概念在有多个目标时，必然存在目标之间的冲突和无法比较的现象，一个解在某个目标上是最好的，在其他目标上却可能是最差的。一个目标的改善往往要以牺牲其他目标为代价，必然不存在每个目标都要达到最优的解，这就是pareto解集的概念，多目标优化问题的解几乎都是一个非劣解的集合，也称为非劣解集。 Pareto最优经常要用到下列相关概念：（1）Pareto支配：解（称作解Pareto支配解），当且仅当，而且，。（2）Parato最优解：解是Pareto最优解，当且仅当不存在，使得。即改进目标函数的同时，必然削弱其他至少一个目标的解，就成为Pareto最优解或者非支配解。（3）Pareto非支配集和前端：设V表示向量集合，则由V中所有的Pareto非支配解的个体所组成的集合就成为Pareto非支配解集。（4）Pareto前沿面：最优集在空间商形成的曲面就成为Pareto前沿面 由以上定义可知，多目标优化问题的Pareto最优解其实只是个不坏的结果，通常情况下，一个多目标问题会有很多个最优解，这就要求在实际情况中根据企业偏好来选择解。特别是在供应链环境下，更加需要决策人员根据各个企业的利益状况和协调供应链体系来进行选择。 在存在多个解的情况下很难说哪个解更优，Pareto最优解是都被认同的。3.2 多目标遗传算法简介3.2.1 遗传算法简介遗传算法由美国学者Holland与1975年首先提出，是一种基于自然生物遗传演化过程的高效率搜索算法，他模拟自然生物的进化过程和机制，借鉴生物界自然选择和自然遗传机制。近些年来，对于遗传算法的研究越来越深入，现在已经普遍的应用到求解多目标优化问题上，效果也很突出。遗传算法主要体现了达尔文的自然选择学说，认为生物群体的进化可以表现为三个方面：第一、适者生存。自然界在不停的变化，只有对环境有较强的适应能力，才有更大的机会被保存下来，在种群中占有的数目才会比较大，而适应能力弱的个体生存下来的机会就会小很多很多。第二、杂交。通过不同个体的交配，子代会继承父代的遗传基因，并且产生一系列新的特征。第三、变异。种群的多样性需要个体的变异，变异会改变种群的基因结构，从而有可能产生更加优化的个体。以上就是遗传算法中最基本的三种操作，下面我们将通过遗传算法的三种基本操作来进行逐一的解释。（1）选择（selection）。在遗传算法中，将仿照自然界适者生