云制造中资源调度问题的算法研究

《云制造中资源调度问题的算法研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

理：ｒ土凃Ｚｈｅ－ｊｉａｎｇＳｃｉＴｅｃｈＵｎｉｖｅｒｓｉｔｙ硕士学位论文Ｍ’ａｓｔｅｒｓＴｈｅｓｉｓ（？）１８９７％／中文论文题目：云制造中资源调度问题的算法研究英文论文题目：ＡｌｇｏｒｉｔｈｍｓｆｏｒＲｅｓｅａｒｃｈＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍｓｉｎＣｌｏｕｄＭａｎｕｆａｃｔｕｒｉｎｇ学科专业：数堂作者姓名：刘淑丹指导教师：蒋义伟完成日期：２０１７年１２月２０日 浙江理工大学学位论文独创性声明本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得浙江理工大学或其他教育机构的学位或证书而使用过的材料一。与我同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。学位论文作者签名：签字曰期：加年月曰／『＋ 学位论文版权使用授权书本学位论文作者完全了解浙江理工大学有权保留并向国家有关部门或机构送交本论文的复印件和磁盘，允许论文被查阅和借阅。本人授权浙江理工大学可以将学位论文的全部或部分内容编入有关数据库进行检索和传播，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。（保密的学位论文在解密后适用本授权书）丨如学位论文作者签名：多＾Ｉ签字日期：州月０日？年令／导师签名：７签字日期：Ｍ年；月／Ｐ日 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究摘要一一云制造是种基于网络，按照用户要求进行服务的种制造新模式。云制造环境下的资源是分散的，可以通过云制造平台把资源整合起来，实现资源使用权的线上交易，有利于资源共享和协同最终实现多方共赢。本文主要研宄在云制造模式下不超过预算成本的平行机调度问题。全文共分为五章。一第章介绍了与调度问题有关的知识和概念以及云制造的相关知识，并总结了近几年关于云制造资源调度问题的研宄成果。第二章主要研宄云制造环境下带有固定加工成本的同类机调度问题，目标是是极小化工时间一。考虑两种情形。第最大完种情形假定工件的长度不完全相同，机器速度越大，其单位成本速度也越大，我们给出了最坏情况界为２１＋的近似算法；第二种情况假（＆）定工件的长度相同但对机器没有要求２１ｅ１－，我们给出了最坏情况界为＋的近似）（）（告；算法。第三章主要研宄带有单位时间加工成本的同类机调度问题。考虑工件是可分的情形，目标是极小化最大完工时间。我们给出问题的最优算法。第四章主要研宄带有单位时间加工成本的同型机调度问题，目标是在不超过成本上限的情况下极大化最小机器完工时间。针对工件可中断情形，我们给出了问题的最优算法。一第五章总结全文并提出相关问题作为下步的的研宄方向。关键词：云制造、调度问题、完工时间、最优算法、近似算法、最坏情况界Ｉ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究ＡｂｓｔｒａｃｔＣｌｏｕｄｍａｎｕｆａｃｔｕｒｉｎｇｉｓａｎｅｗｍａｎｕｆａｃｔｕｒｉｎｍｏｄｅｌｂａｓｅｄｏｎｔｈｅｎｅｔｗｏｒｋａｃｃｏｒｄｉｎｔｏｇ，ｇｔｈｅｎｅｅｄｓｏｆｕｓｅｒｓ．Ｒｅｓｏｕｒｃｅｓｉｎｔｈｅｃｌｏｕｄｍａｎｕｆａｃｔｕｒｉｎｇｅｎｖｉｒｏｎｍｅｎｔａｒｅｄｅｃｅｎｔｒａｌｉｚｅｄ，ａｎｄｒｅｓｏｕｒｃｅｓｃａｎｂｅｉｒａｔｅｄｔｈｒｏｕｈｔｈｅｃｉｉ？ｎｔｅｇｇｌｏｕｄｍａｎｕｆａｃｔｕｒｎｇｐｌａｔｆｏｒｍｔｏｒｅａｌｚｅｏｎｌｉｎｅｔｒａｎｓａｃｔｉｏｎｏｆｒｅｓｏｕｒｃｅｕｓｅｒｉｇｈｔｓｗｈｉｃｈｉｓｂｅｎｅｆｉｃｉａｌｔｏｒｅｓｏｕｒｃｅｓｈａｒｉｎａｎｄｓｎｅｒ，ｇｙｇｙｔｏａｃｈｉｅｅｗｉｎ－ｉｔｃｏｓｖｗｎｏｕｍｅ．Ｔｈｉｓｔｈｅｓｉｓｍａｉｎｌｙｓｔｕｄｉｅｓｔｈｅｐｒｏｂｌｅｍｏｆｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｆｏｒａｉｖｅｎｂｕｄｅｔｔｏｔａｌｃｏｓｔｉｎａｃｌｏｕｄｍａｎｕｆａｃｔｕｒｉｎｅｎｖｉｒｏｎｍｅｎｔ．ｇｇｇＴｈｅｔｈｅｓｉｓｃｏｎｔａｉｎｓｆｉｖｅｃｈａｐｔｅｒｓ．Ｉｎｃｈａｐｔｅｒｌｗｅｆｉｒｓｔｉｎｔｒｕｄｕｃｅｓｏｍｅｂａｓｉｃｃｏｎｃｅｔｓｏｆｔｈｅｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍａｎｄｃｌｏｕｄ，ｐｇｐｉａｎｄｓｕｍｍａｒｉｚｅｉ？ｍａｎｕｆａｃｔｕｒｎｇｔｈｅｒｅｓｅａｒｃｈｒｅｓｕｌｔｓｏｆｃｌｏｕｄｍａｎｕｆａｃｔｕｒｎｒｅｓｏｕｒｃｅｓｃｈｅｄｕｌ，ｇｉｎｇｉｎｒｅｃｅｎｔｅａｒｓ．ｙＩｎｃｈａｐｔｅｒ２ｗｅｍａｉｎｌｓｔｕｄｕｎｉｆｏｒｍａｒａｌｌｅｌｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｓｗｉｔｈｆｉｘｅｄ，ｙｙｐｇｐｍａｃｈｉｎｅｃｏｓｔａｎｄｔｈｅｏａｌｉｓｔｏｍｉｎｉｍｉｎｚｅｔｈｅｍａｋｅｓａｎ．Ｗｅｃｏｎｓｉｄｅｒｔｗｏｃａｓｅｓ．Ｔｈｅｆｉｒｓｔ，ｇｐｃａｓｅａｓｓｕｍｅｓｔｈａｔｔｈｅｏｂｓｗｉｔｈｄｉｆｆｅｒｅｎｔｓｉｚｅｓａｎｄｔｈｅｍａｃｈｉｎｅｗｉｔｈｆａｓｔｓｅｅｄｈａｓａｇｒｅａｔｅｒｊｐｉ－ｕｎｔｃｏｓｔｓｐｅｅｄ．Ｗｅｇｉｖｅａｎａｐｐｒｏｘｉｍａｔｉｏｎａｌｇｏｒｉｔｈｍｗｉｔｈｗｏｒｓｔｃａｓｅｒａｔｉｏｏｆ２１＋（占）；Ｔｈｅｓｅｃｏｎｄｃａｓｅａｓｓｕｍｅｓｔｈａｔｔｈｅｏｂｓｈａｖｅｔｈｅｓａｍｅｓｉｚｅｓａｎｄｗｅｉｖｅａｎａｒｏｘｉｍａｔｉｏｎｊｇｐｐ—ａｌｏｒｉｔｈｉｔｈｗｏｒｓｔ－ｃａｓｅｒａｔｉｏｏｆ２１＋ｅｌｇｍｗ（）（Ｉｎｃｈａｐｔｅｒ３ｗｅｍａｉｎｌｓｔｕｄｕｎｉｆｏｒｍａｒａｌｌｅｌｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｓｗｉｔｈｕｎｉｔ，ｙｙｐｇｐｔｉｍｅｐｒｏｃｅｓｓｉｎｇｃｏｓｔ．Ｗｅｃｏｎｓｉｄｅｒｔｈｅｃａｓｅｗｈｅｒｅｔｈｅｏｂｓａｒｅｆｒａｃｔｉｏｎａｌａｎｄｔｈｅｏａｌｉｓｔｏｊ，ｇｍｉｎｉｍｉｎｚｅｔｈｅｍａｋｅｓｐａｎ．Ｗｅｇｉｖｅａｎｏｐｔｉｍａｌａｌｇｏｒｉｔｈｍｏｆｔｈｅｐｒｏｂｌｅｍ．Ｉｎｃｈａｐｔｅｒ４ｗｅｍａｉｎｌｓｔｕｄｉｄｅｎｔｉｃａｌａｒａｌｌｅｌｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｗｉｔｈｕｎｉｔ，ｙｙｐｇｐｔｉｍｅｐｒｏｃｅｓｓｉｎｇｃｏｓｔａｎｄｔｈｅｇｏａｌｉｓｔｏｍａｘｉｍｉｚｅｔｈｅｍｉｎｉｍｕｍｍａｃｈｉｎｅｃｏｍｌｅｔｉｏｎｔｉｍｅ，ｐｗｉｔｈｉｎａｉｖｅｎｃｏｓｔ．Ｆｏｒｒｅｅｍｔｉｖｅｃａｓｅｗｅｒｏｖｉｄｅａｎｏｔｉｍａｌａｌｏｒｉｔｈｍｏｆｔｈｅｒｏｂｌｅｍ．ｇｐｐ，ｐｐｇｐＩｎｃｈａｐｔｅｒ５ｗｅｓｕｍｍａｒｉｚｅｔｈｅｆｕｌｌｔｅｘｔａｎｄｕｔｆｏｒｗａｒｄｔｈｅｒｅｌａｔｅｄｉｓｓｕｅｓａｓｔｈｅｎｅｘｔ，ｐｒｅｓｅａｒｃｈｄｉｒｅｃｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：Ｃｌｏｕｄｍａｎｕｆａｃｔｕｒｉｎｇ；Ｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍ；Ｍａｋｅｓｐａｎ；Ｏｐｔｉｍａｌａｌｇｏｒｉｔｈｍ；ｉｉ－ｉＡｐｐｒｏｘｍａｔｅａｌｇｏｒｔｈｍＷｏｒｓｔｃａｓｅｒａｔｏ．；ＩＩ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究目录摘要ＩＡｂｓｔｒａｃｔＩＩ１绪论１１．１１调度问题概述１．２算法设计与分析２１．３云制造简介３１．４云制造资源调度问题模型及其相关研宄４１．５论文结构６２带固定机器租用成本的同类机调度问题７２．１引言７２．２符号定义７２．３ＱｍＵ＜ＵＣｍｓｘ８＼＼＝２．４ＱｍＵ＜ＵＣｍａｘ１０，ｐｊｐ＼＼２．５１３本章小结３带单位加工成本的同类机调度问题１４３．１１４引言３．２１４符号定义３．３＜？７＾［／＜（７＿最优算法１５３１／，｜０３．４本章小结１９４带单位加工成本的同型机覆盖问题２０４．１引言２０４．２２０符号定义４．３Ｐｍｐｍ加优算法２１，｜４．４２５本章小结５总结与展望２６参考文献２７ＩＩＩ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究附录３１致谢３２ＩＶ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究第１章绪论１１．调度问题概述运筹学范畴的一上发展调度问题ｓｃｈｅｄｕｌｉｎｇ又称排序问题，是个重要分支，是国际（）一最快速、研宄最广泛、研宄结果最丰富、最有前景的学科领域之。随着制造业的发展，经典的排序问题已经被突破，新的问题相继出现，受到更多的理论工作者和实际工作者的关注。它在大部分的制造系统、生产系统和信息处理系统中起着重要的作用。它同样存在Ｍａ一些新兴领域中于运载配送、管理科学、计算机科学、工程技术和ｐｒｅｄｕｃｅ等。一调度问题是指利用些处理机ｐｒｏｃｅｓｓｏｒ、机器ｍａｃｈｉｎｅ或资源ｒｅｓｏｕｒｃｅ，最优地（）（）（）一一些限制加工批接收到的任务ｔａｓｋ或工件ｊｏｂ。在加工这些任务或工件时要求满足（）（）工件的到达时间、规定的完工时间、工件的加工次序、资源对加工时间的影条件，如响等。最优加工指的是通过处理任务使目标函数达到最大或最小，而目标函数通常是“”表示加工时间长短三参ｔｈｒｅｅ－ｆｉｅｌｄ、处理机的利用率等。调度问题通常用数表示法（ｒｅｒｅｓｅｎｔａｔｉｏｎｏ；３１〇；表具体的机器环境、工件特征和ｐ／７来表不，其中，，７分别代）／／［］最优准则，这是调度问题的三个组成部分。ａｓｉｎｌｅｍａｃｈｉｎｅ、平行机ａｒａｌｌｅｌ域规定了机器环境，常见的机器类型有单台机（ｇｐ）（ｍａｃｈｉｎｅ、流水作业ｆｌｏｗｓｈｏ、异序作业ｏｂｓｈｏ、开放作业ｏｅｎｓｈｏ等）ｐｊｐｐｐ。根据力口（）（）（）工速度不同可分为三种类型一ｉｄｅｔｉｃａｌ：当所有的机器都是样的速度时，称之为同速机ｎ（一ｍａｃｈｉｎｅｓ当机器的速度不且每个机器的速度都是固定的工的工，而，不受加；样时）件影响，称之为恒速机；当机器的速度受加工的工件影响时，称之为变速机ｕｎｒｅｌａｔｅｄ（ｐｒｏｃｅｓｓｏｒｓ２。）［］卢域规定了加工的约束条件和限制，例如工件的提交日期，工件是否可中断、工件是否可分和机器是否有故障等。依据工件在调度加工的过程中是否可中断分为可中断排序ｐｒｅｅｍｐｔｉｖｅｓｃｈｅｄｕｌｉｎｇ、不可中断排序ｎｏｎ－ｐｒｅｅｍｐｔｉｖｅｓｃｈｅｄｕｌｉｎｇ。可中断排序指的（）（）是不需要把一工件在它完工之前全部放在同一台机器上加工个，可以在任意时刻进行中断，，然后把别的工件放在这台机器上加工同时中断的部分可以在之后的任意时刻放在别的机器上进行加工一工件从加工，且之前加工完的部分不会丢失。不可中断排序指的是个一台机器上连续加工开始到结束的过程中不可以中断，必须放在同。根据工件预先知道的ｏｆｌｉｏｎｉｉ－ｉ信息分为离线排序ｎｅ，在线排序ｌｎｅ和半在线排序ｓｅｍｏｎｌｎｅ。离线排序指的（（））（）是在开始加工任务的时候已经知道工件的全部信息，在线排序指的是在开始加工任务的时候不知道工件的任何信息工任务的时候只知道工件的一，半在线排序指的是在开始加部分信息。１ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究表示调度问题的目标函数一７域，指的是在规定的约束条件下，为了完成某个绩效一？指标找到问题的个最优排序。比如，在调度运行的过程中，工件在机器风上加工时间记为（７工时间记为Ｇ工时间ｍａｋｅｓａｎ记为＝／，机器风的完，机器的最大完ｐ（）工时间记为一ｍｏ＾Ｃ，最小完＝本文主要研宄两种目标函数，个是极小化最＾工时间一工时间（机器覆盖）。在其他调度问题中比较常大完，另个是极大化最小机器完见的目标函数有最大延迟、加权总完工时间、加权滞后工作数量等３。（）（）［］１．２算法设计与分析对于调度问题的计算复杂性理论研宄开始于上个世纪六十年代，算法的设计与分析与之有着密不可分的联系。随着算法的理论性研宄的加深，数学界的学者对于Ｐ问题和问题的讨论日益激烈。其中ｐ问题指的是可以在多项式时间内可解的问题，如一果尸＃尸ＡＴＰ－＃，那么难问题指的是不能在多项式时间内找最优解的类问题。同时有了更多的学者同意ｐ的猜想，但是应该用什么方法验证ｐ的猜想是正确的至今一２１４。都没有找到，这个猜想也被国际数学界列为世纪最根本的几大问题之在实际生活［］一中有很多＃尸问题ａｒｏｘｉｍａｔｉｏｎａｌｏｒｉｔｈｍ，因而这就要求我们设计出种近似算法ｐｐｇ来处（）理此类问题法ｏｔｉｍａｌａｌｇｏｒｉｔｈｍ最大程度上接近的算法。，即尽量找到与最优算ｐ（）一一调度问题的算法指的是预先设计个执行程序，对于调度问题的任意个实例，通过一这个运行程序得到种可行性排序。调度问题主要有两种分类即在线问题、离线问题，与之对应的算法是在线算法、离线算法。Ｇｒａｈａｍ在１９６６年提出了解决在线问题的算法阆，１９６９年提出了解决离线问题的算法７。算法指的是工件的到达顺序是未知［］的，而且工件的长度等信息也不能预先知道，在求极小化最大完工时间的时候，则把工件放在可以最早完工的机器上面。算法指的是工件的长度和到达时间是已知的，把工件按照长度从大到小的顺序排序，然后把工件依次放在可以最早完工的机器上面加工。判断一个近似算法好不好有两个标准，即算法的时间复杂度和算法得到的近似解与一一最优解的接近程度般来说用最坏情况界ｗｏｒｓｔ－ｃａｓｅｒａｔｉｏ。，我们来判断个算法的好（）坏。如果算法４是解决一个极小化问题的近似算法，那么称＝＞ｐＡｉｎｆ｛ｐ一是算法４的最坏情况界ｗｏｒｓｔ－ｃａｓｅｒａｔｉｏ，如果问题是个在线或半在线问题，则称为（）４的ｃｏｍｅｔｉｔｉｖｅｒａｔｉｏ５表示这个实例：Ｚ：通过算法Ａ算法竞争比（ｐ，假设与分别）［］＊（。操作得到的目标值和离线情形的最优目标值，为了方便分别简记为和７同时，假如２ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究问题的目标函数是极大化问题，可以称＝ｐＡｉｎｆ＞＜Ｔ｛ｐＰ，Ｖ｝是算法４的在离线问题中的最坏情况界，也可以称为在线问题的竞争比，同时是半在线问题中的竞争比。１３云制造．简介近年来，云计算、物联网、信息物理系统、虚拟化技术等先进技术被提出，而且发展速度很快，对许多其他行业产生了很大的影响。制造业与这些先进的信息技术相结合，由此产生了计算机集成制造、敏捷制造８９虚拟制造１０１１网络制造、制造网格和云，，．丨卜丨卜一些新的制造模式制造等。＾种新的制造模式云制造作为，主要包括三个重要的部分：云制造服务平台、资源提供者和制造商。云制造主要包括机器使用权在线交易和离线制造两个方面。也可以称—一作０２０〇ｎｌｉｎｅＯｆｌｉｎｅ的制造形式。云制造系统是个以服务为基础，能够面向全球用（）户，可以进行商业运作的新系统。资源提供者可以把制造资源的使用状态比如空闲或繁忙，进行虚拟化发布到云制造平台上，通过云制造平台进行交易获得利润。制造商把自己的需求发布到云制造服务平台上，云制造平台根据制造商的要求进行匹配资源，然后制造一定的租赁或者购买费用才能获得资源商支付。因此制造商可以通过云制造平台获取空闲的资源来处理制造任务。云制造平台的运营方为资源提供者和制造商提供服务，需要收取相应的服务费用。具体的云制造服务平台的运作流程可以参看图１．１。对于制造商来说，云制造蹏务平台［眼务平台ｎ户核心业务资源注册需求发布多向搜溱能力评估｜１１１１１１｜｜企业注册用户筲理１１｜ｉ？用ｉｆ估设■謂协作结算關资源提供方丨丨丨ｊ｜｜｜＿求方｜１ｊＨ用户设胥流程设置规則设置ｉ？ｉｉ权限设晋服务计费｜：丨以Ａ｝＼丨艺ｆ求１｜｜？ｓｊ资源虛化资源蔣求描述ｒｓｓ要ｉ！（ｐ一／Ｉｔｕｔ＝誌５＾］业务协怍＞工序＞工序Ｉ＊＞Ｘ序！ｉ＞＞＞、＞＂务＼住务將任务Ｊ任备Ｊ｜｜｜｜｜Ｈ＇ｉ〇１〇ＴＩＩＭ［应用集成应用集成应用集成＾ｉＣＡＤＲＥＥＫＰ｜ｉｊ１．１图：云制造服务平台的运作流程云制造平台可以帮助他们在全球范围内找到高价值、低成本的资源，实现绿色、髙效、智３ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究能的制造过程。通过整合离散的空闲资源，可以使制造商形成更大的生产能力，获得更高的利润，这有利于促进资源的共享与协作。对于政府来说，云制造平台可以提高管理区域制造资源的效率，对于节约资源意义重大。１４云制造资源．调度问题模型及其相关研究在云制造环境下，文章主要研宄了受加工成本预算限制的调度问题。制造商从顾客那里得到自己需要完成的任务，然后制造商通过云制造平台获取自己需要的资源。但是制造一定的租用费用商利用资源是需要支付，由于制造商有预算成本上限，那么对制造商来说租用资源的费用越低越好，同时希望顾客的满意度越高越好。这就需要我们进行分析使得制造商和顾客双方的要求都能满足。制造商租用的资源相当于完成任务所需要的的机器，从顾客那里获得的任务就相当于需要加工的工件，租用的机器总费用相当于加工的总成本。有的机器的租用成本是固定的不受加工时间的限制，但是有的机器的加工成本是与加工时间是相关的即加工时间越多加工的总成本越大。以上描述的模型就是云制造资源调度问题的模型一工件放在机器上加工。我们需要给出个算法，按照算法的步骤把，提高顾客满意度的同时不超过给定的预算成本。本文所研宄的问题就是在上述描述的模型条件下进行的。第二章研宄的带有固定成本的云制造资源的同类机调度问题，目标是极小化最大完工时间，最大完工时间越小说明顾客等待的时间越短，则顾客的满意度越高。第三章研宄的是带有单位时间加工成本的云制造资源的同类机调度问题，目标函数是极小化最大完工时间，也是为了提高顾客的满意度。第四章研宄的是带有单位时间成本的云制造资源的同型机调度问题，这个问题的目标函数是极大化最小机器完工时间（机器覆盖），有的机器加工系统要求所有的机器都要保持同时运行，比如飞行器的燃气涡轮发动机系统、计算机的网络宽带分配系统等。机器的最小完工时间越大说明所有机器同时运作的时间越长，有利于系统的稳定运行。近年来云制造资源调度问题已经引起国内外大量研宄者的关注。李伯虎等１２１７，根［］一些建议据我国工业的发展状况，针对云制造模式在我国的发展提出了。１９９９年Ｎｏｇａ一工成本记等１８首次在生产调度问题中引入了加工成本的因素，每台机器都有个固定加［］作常数１在线情况下求极小化最大机器完工时间的调度问题放时，研宄了，当机器不带释间的时候竞争比为，带释放时间的情况下的竞争比为。２００６年Ｉｍｒｅｈ１９把机［］器的固定成本为一１的条件去掉，考虑两种不同加工成本的机器，其中种机器的成本比另一工工件的时候尽可能多的选择加工成本较低的机器种机器的加工成本高，在加，但是也用一部分成本较高的机器加工工件。Ｊｉａｎ２０研宄了可中断情况下在线调度问题ｇ等，目标函数是极小化总完工时间和极［］小化机器总加工成本一，文章假定机器的加工成本与机器的数量是线性关系，给出了个新４ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究１．３。Ｄｏｓａ２１算法，并得到算法的竞争比为７９８，问题的下界为等继续研宄了在线调度｜［］问题一，目标函数是极小化最大完工时间和机器总加工成本，设计了个新算法，得到问题的下界为力１．５４８６，改进了之前的问题下界并且得到问题的竞争比为，改进了｜，之前算法的竞争比＾＾１．５７９８。Ｊｉａｎｇ等２２研宄了在线调度问题，目标是极小化机器［］总完工时间和加工总成本，针对工件可中断、不可中断的情况，得到了可中断和不可中一断的算法的竞争率至少为１．５工件不可中断的时候，当，给出了个在线算法，其竞争比一为１．６４０３的１．５６５４，当工件可中断的时候，给出了个在线算法，其竞争比为，同时证明了这两个算法的竞争比都是紧的。Ｒｕｓｔｏｇｉ等２３研宄了增加机器数目对极小化最大完工时间和总完工时间的影［］一响。Ｊｉａｎｇ等２４把问题扩展到半在线情况，预先知道工件的总长度，假设购买台器的［］成本为单位数量一些结１，目标是获得极小化总完工时间和最小的购买机器的成本，得到论。Ｈｅ等２５考虑了单台机的平行机调度问题，机器允许拒绝加工的工件，但是要支付［］相应的拒绝处罚成本一工，目标函数个是在不达到给定的处罚成本上限的情况下使得总完时间尽可能的小一工时间的情形下，另个是在不达到预先给定的完，使得机器的总处罚成本最小，给出了问题动态规划算法和完全多项式时间算法。Ｅｌｖｉｋｉｓ等人２６在２０１１年针［］对平行机的极小化最大完工时间和极小化机器总加工成本调度问题给出了多项式时间算一工时间和极ｅｅ２７法。Ｌ等考虑了平行机调度问题中双目标函数问题，个是极小化总完［］小化机器的总加工成本一工时间和极小化加工总成本，另个是极小化机器最大完，给出了问题的启发式算法和最坏情况界ｔａ２８研宄了流水车间中，在极小化最大完。Ｇｕｐ等人［］工时间情形下使得机器的租赁总成本最小的双目标调度问题一。，给出了个启发式算法Ｌｉ等２９以大数据和云制造技术为背景，研宄了平行机调度问题，每台机器的加工成本也［］是相对独立的，其目标是最小化总误工时间和总加工成本，给出了问题的模型和解决方案。针对极大化最小完工时间的平行机调度问题一，许多学者对于经典的排序问题做了些研宄。对于离线情况下的调度问题，问题Ｐｍｐｍｔｎ（７ｍｉｎ是在多项式时间内可解。对｜｜＂ＣｆＤ１尸７于问题■Ｐｍｍｉｎ，ｅｕｅｒｍｅｙｅｒ等人３０给出了算法，证明了算法的最坏情况界不超｜｜［］１Ｗｏｅｉｎｅｒ３ｌ证明了［Ｐｒ算法的紧界为Ｗｏｅｉｎｅｒ３２证明了在线情况下ＬＳ过，ｇｇｇｇ蠢［］［］，。对于问题＿Ｐｍｍｔｎ（７ｍ，Ｊｉａｎｇ等３３算法是最优的给出算法的竞争比为ｍｐｉｎ给出了该｜｜［］问题的下界并给出了在线情况下的两台同类机的最优算法。对于半在线情况下的调度问题，Ｈｅ等［３４］给出了两台平行机半在线情况下的机器覆盖问题的最优算法。Ｃａｏ等［３５］研宄了半在线情况下预先知道工件的最大长度的两台平行机的机器覆盖问题，文章给出了问题的算法和下界。２００６年Ｔａｎ等３６研究了预先知道工件总长度的两台机的半在线机器覆［］盖问题。在２００７年Ｔａｎ等３７研宄了机器数ｍ２３的半在线机器覆盖问题，当预先知道工件［］５ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究一的总长度或者工件的最大长度中的ｍ－１个条件时，给出了竞争比为的近似算法，当开始加工之前知道所有工件的长度、最长工件的长度时，对于三台机器参与加工运行的调度问题，给出竞争比为的近似算法，对于ｍ２４台机器参与加工运行的调度问题，给出竞｜－２３８研宄了中断次数受到限制争比为ｍ的近似算法。Ｊｉａｎｇ等，求极大化最小机器完工［］＾时间的问题ｉ，针对ｍ台同型机中断次数为情况，给出了最坏情况界为＾的近似算法。１．５论文结构一一些基础概念知识一第章：绪论。介绍有关调度问题的、云制造资源调度问题的些背景、意义、模型。第二章：云制造资源受限的带有固定加工成本的同类机调度问题，目标是极小化最大完工时间。针对工件的长度是否相同两种情况进行研宄。当工件长度不完全相同时，且机一个近似算法器的速度越大，机器的单位成本的速度也越大，本章给出了，最坏情况界２一为１＋。当工件长度相同时，，且对机器的速度没有要求本章也给出了个近似算（＆）２１＋ｅｌ－上述结果对于已有文献给出的结果作出了改进。法，最坏情况界为。）（）（￡：云制造资源受限的带有单位时间加工成本的同类机调度问题第三章，目标是极小化最大完工时间。针对工件长度不相同且是可分的情况，本章给出了问题的最优算法。第四章：云制造资源受限的带有单位时间加工成本的可中断的同型机调度问题，目标是极大化最小机器完工时间，本章给出了问题的最优算法。一些不足一第五章：概括全文，对下，提出本文存在的步的研宄目标进行展望。６ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究第２章带固定机器租用成本的同类机调度问题２１．引言一本章主要研宄云制造环境下带有固定租金的同类机调度问题。每台机器都有个加工速度和固定的租用成本，其中固定租用成本不随加工时间变化而变化。云制造平台提供ｍ台机器，机器集合表示为抓＝抓１，抓２广、７１４１。机器风的加工速度｛｝为＾，固定的租用成本为从顾客那里获得的需要加工的ｎ个工件，工件集合表示＿＝．．．．．．工件＝＜７＜７＜７＜７＜１２为１７１。７７１，放在加工速度为单位１的机器上进行加｛，２，，｝，，，？〇）工工时间记为工件ｍ台工一一，其加巧。这ｎ个，都可以放在机器上进行加，但同时间个一一一一工件一工件只能放在台机器上加工。租用些机器加工，台机器同时间只能加工个工件一些机器的总加工成本记为［／。资源，这制造商的成本预算是个固定常数Ｇ目标是（），在不超过给定的总预算成本Ｇ的情况下使得最大完工时间最小。本章分为两种情况进行研一宄，第种情况假设工件的长度不完全相同，机器速度越大，其单位成本速度也越大，问题可以用符号表示。第二种情况是工件的长度相同但对机器没有要求，问＝Ｃ表示题可以用符号Ｓ仏巧ｐｍａｘ。｜Ｌｉ等３９研宄了云制造环境下同类机的调度问题，目标函数是极小化最大完工时间，［］工件的长度都相同为一假设每个个固定的常数，每台机器的租用成本是固定的但不相同，不随加工时间发生变化，机器速度越大，相应租用加工成本越高，对于可中断和不可中断两种情形，分别给出近似算法和最坏情况界。一一本章研宄的两种调度问题是文献３９所提问题的更般的情况。第种情况假设工件［］的长度不完全相同，机器速度越大，其单位成本速度也越大；第二种情况假设工件的长度相同，但对机器速度的大小顺序没有要求。本章对于上面两个问题分别给出了近似算法和最坏情况界分析。２３本章内容安排：第部分给出了问题用到的符号定义第部分给出了问题＾“以＾；＝Ｃ的近似算法；第４部分给出了问ｇ仏巧ｐｍａｘ的近似算法；第５部分对｜全章进行概括。２．２符号定义为了具体描述云制造资源同类机调度问题：，引入以下符号ｍ：云制造平台提供的的机器数量；ｎ：制造商需要加工的工件数量；ＴｋＴ＝７１＾财…云制造平台提供的机器集合；｛，２，，７ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究＝…？／《／：制造商需要加工的工件集合九２；｛，，人｝工件Ｊ＋：的长度巧；，Ｖ机器风的加工速度，即单位时间加工的工件长度；：机器风的固定租用成本；＆给定的总预算成本；［／：机器加工工件需要的总成本；机器风的负载；ＣｍｃＭ：算法义的目标函数值靈⑷（？＿；ｏｐｔ：最优调度的ｍａ／ｃｅｓｐｃｍ。（）２．３Ｕ＜ＵＣＱｍｍａｘ＼＼一＝在这节中，我们考虑Ｑｄｔ／ＳＲＣｍａｘ问题。设ｎ个工件的总长度为尸￥。爪台＾＝１巧Ｓ？？？Ｓ且机器速度越大其单位成本速度也越大机器的速度满足＆２２２２ｍ，并，即ｆ２目标函数是指在不超过给定的总预算成本＾的情况下使得最大完工时间最小。对于此类问题，首先选择需要租用的机器，用ＡＴ表示选择的机器集合。这些机器的总加工成本／［不超过给定的成本上界Ｇ，即。注意到有的机器的速度虽快工成本超过了给定的成本上界一但其加，则这些机器就不能被租用。此时用／Ｉ表示第个不■？？？。ＳＳ被选择的机器，这台机器的速度为办由假设可知Ａ２２２２ｍ，齡２，因此在机器之后被选择的机器的速度和不超过办ＴｋＴ中机器的数量。这样问。用ａ表示集合题＜Ｕ为（７。９ｍＳ可以简化Ｑａｍａｘ下面设计算法木来解决这个问题。｜｜｜算法４７＝＝＝＝Ｓｔｅ１．［／０／ｉ０７Ｗｉ１ｐ令，，４，；Ｓｔｅ２■／＋ｇＧＴｋＴ＝ＴｋＴ如果［，则，ＵＵ＋ｐ；Ｕ风＆一Ｓｔｅ３．ｉ＋＋ｉｍ２ｐ，若ｇ，返回第步；；否则进行到下步Ｓ＝ｔｅ４■／＞ｐ令ｉＧ；｝５＝Ｍ……Ｓｔｅ■记ａ从ＴｋＴ＝７１—，其ｐ，选择的机器集合抓４，ｓ，，ｉＵ２，，叫Ｊ｜｜｛｝｛｛岣”叫中Ａ＂－１＝＞．．．＞＞＂：＋ａ且Ａｊｎ＞Ａ；６…Ｓｔｅ．把工件按照其加工时间从大到小进行排序即仍２Ｐ２２２Ｐｎｐ；＝＝＝Ｓｔｅ７．１对任意的１ｉａ０厶ｐ令，山表不第ｉ个有序工件集合，心表不ｊ；ｇｇ令心丨第ｉ个有序工件集合Ａ的总的加工时间；８ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究．．８＝？＝Ｓｔｅ■设＋，则／＋工ｐ々ｂ；？：；告］ｇ？一Ｓｔｅ９．ｎ止。ｐ若ｇ，则返回第上步，停ｊ；否则在给出算法的最坏情况界之前，首先给出问题＾＾匕＾的最优解辦）的下界和算法的目标函数值的上界，用Ｍｗ表示选择的ａ台机器中的第ｉ台机器，，表示对应的加工速度。Ｐｎ１－＜２（２引理．１７〇ＣｍａｘＡ（）匪“辦）２－（）｛ｉ）Ｓ＋ｓｇｇ＾＾ｆｉｈ＝…１ｒ表ｒＴｋＴ证明：令示前／ｉ台机器Ｇ集合，即＾地媽设表示最优排序（）＾，，，中的机器集合。根据假设可以得到＾ｉ２－Ａ。又Ｃｍｃｏ辦）２，故；ＥｉｅｒＤｅＭ＾ＳｊＰ＇Ｃｍａｘｏｐｔ｝｛ｓ／ｖｉｉｅｒ所以ＰＣ〇ｐｔｋ￣ｍａｘ（）＾ｈｌｓ＋ｓＹ，ｉｈ＝ｉｌ一工的工件Ｗ２设工件人是最后个加。用Ｃ表示在加工人工件之前的机器的完工（）＝１．．．上进行加工＝时间纟２心如果把工件７１，１＜６＜＾即（＾义，，，，人放在机器＾（１％］）＾Ｃ＝．．．＋。根据五ＣＴ规则，对任意的ｉｌ２ａ，严，，，都有ｂ［ｋ］ｋ［］ＷＣＡ＝Ｃ＋—＜Ｃ＋ｍａｘ）（Ｓ？ｋｉ［］［］化简可得＾４＾ｌ）ｉ＾＾ｉＰｎ（［］［］由此可推出ａａ＜ｗＣｍ－＾－ｌＳｃ＾ｚ＾Ｐｎｍａｘｉ（）［］［］ＥＥ＝ｉ＝ｉｌｌ由ａｎ—ｌｌＣ［］Ｓ＋＝ａ￣ｌＷａＰｎＰｊ＋Ｐｎ＋Ｐｎ，＾２＾２（）ｉ＝ｌｊ＝ｌ可知ａＣ＜Ｐ＋－ｌ－＾－ｌ？ａｎｍａｘｉｐ，（）［］（）Ｅ＝ｉｌ９ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究因此ｐ＋￣１Ｐｎ＜）＾ｚ＾ｉ＝ｓｌｂ］．又因为ｈ—ｌａＳ５３ｉ—＾２ｉ＝ｌｉ＝ｌ所以，ｐ＋￣１Ｐｎ＜）Ｘ－ＳＺ＾ｉｉ＝ｌ引理得证。口定理２．２ＣｍａｘＡｉＣｍａｘｏｐｔ＜２１＋Ｔ．（）／（）（＾ｉ）证明：由引理２．１可知Ｐ－－ａ－ｌ＼（）ｐｎ＾ｈｌＪ２＾ＣＣ〇ｐｔ－／ｍａｘ｛）＾ｐ，￣ｈ＾ｌＳ－－ｓＹ＼ｊｉｈ＝ｌｉ化简可得ｎＦ＋１Ｓｈ（ＫＥ＜？ＣＡＣ〇Ｐｔ－ｍａｘｉｍａｘＶ（）／（）＾尸ｈＴｓ２＾＝ｉｉｉ又根据Ｐ＋ａ－ｌｐｎ（）＜２ｐ－和＾ｓ＋Ｓｈｓ＝＝１＜１＋＜１－＾＋＋．＼＼ｈ＼－－Ｌｈ－ｌＥｔｉ、Ｅｔｉ、可以得到Ｃｍａｘ＾－ｌＣｍａｘｏｐｔ＾２１＋■（）／（）（＾定理得证。口２＝．４ＱｍＵ＜ＵＣｍａｘ，ｐｐ＼ｊ＼一ｔ／＝ＣＢ．＝这小节研宄Ｑｍｇ仏巧ｐｍａｘ问题，考虑工件长度相同的情形，Ｐｐｐ。｜｜，在这个问题中，对机器没有约束条件，即机器速度和固定租用成本是任意的，目标是在不超过给定的总预算成本Ｇ的情况下使得最大完工时间ｍａ／ｃｅｓｐｃｍ最小。（）一Ｂ有一与上节的问题类似，假设租用的机器集合为，则。用／＾表示第。６个不被选择的机器，这台机器的速度为办用表示集合Ｂ中机器的数目，问题可以简化１０ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究为＾＜。下面设计算法来解决这个问题。６＾＾｜｜算法ｌ＝．．．■ｉｌ２ｍ的大小进行非增的顺序重新排序Ｓｔｅｐ把机器按照，即满足齡，，，＾＾２＞．＞．．．＞１＾．＞Ｋ－－－！Ｋ２Ｋｍ＝＝＝＝Ｓｔｅ２■［／０／ｉ０Ｂｉ１ｐ令，＿，；；０３＝５＝３七６．／＋７如果［＾５＆，以以＋？，则５口风＆；一４＝Ｓｔｅｉｉ＋１，若ｉｇｍ３步ｐ返回第；否则进行到下步；，＂＝ｍＳｔｅｐ５■令／ｉａｒ々ｉｎ［／＋＞０｛｝；６＝Ｂ＝……财Ｓｔｅ．记６７１ｐ，选择的机器集合＾地—，其间｛，，，４ＪＵＵ外，碼；，，｝；＾－＝．．．中Ａ：＋＂１６且＞＞＞＞／ｉ；％乂＝＝＝Ｓｔｅ７．１１ｉ６０厶表不第ｉ个有序工件集合，表不ｐ令ｊ；对任意的ｇｇ，令々山丨心第ｉ个有序工件集合Ａ的总的加工时间；．．＝？＝＝＝Ｓｔｅ８■设ａｒｒｏｉｎ＋１ｐＺｇＵｔ＋，则Ａ心ＵＰ，勺勺＋；ＪＪ；｝吾Ｊ９一Ｓｔｅ．若ｎ上ｐｊｇ，则返回第步；否则，停止。同样地，我们首先给出问题Ｑ６Ｃｍａｘ的最优解Ｇ的下界和算法烏的目标函数值的ａｘ｜｜上界＊财。设最优解的机器集合为Ｂ，用＾表示根据算法烏选择的６台机器中的第ｉ台机器，，表示对应的加工速度。引理２．３１心似（〇辦）２（２ＣｍａｘＡ２＜（））（）证明：１由于每个工件的长ｉ都相等为ｐ，则ｎ个工件的ｉｉｉ为ｎｐ，显然有（）Ｃｏｐｔ＞（）＊ｉｅＢ一２设工件入是最后个加工的工件，它的完工时间决定了最大完工时间。用表（）财ｉ＝１２＾６示在加工工件人之前的机器的完工时间，。如果最后把工件人放在机＾，＾，器财＾上进行加工，１ｇＡ：ｇ６，即＇Ｃ＾＝ｍａｘ－２（）ｓｍ１１ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究＝…则对任意的ｉ１２６，都有，，，ｋ＾＾ＣＡ＝Ｃ［］＋＜Ｃ＾＋ｍ＆Ａ２），ＳＳｉｆｃｉ［］［］化简得＇＾＜＾Ｃｍａｘ－２＾ＣＳ＋ｊｐ（）［］ｙ＾．由此可得ｂｂ＾＜—ｌ＜—１ＣｍａｘＡＣＳ＋ｂｎｂｎ＋ｂ．２＾｛ｐｐ＋ｐｐ（）［＼（）（）＾Ｘ］＝＝ｉｌｉｌ因此Ｅｓｗ＝ｉｌ□２１１—定理．４乞２＋６（）（忐）证明：由引理２．３可知ｎ－－ｂ－ｌ（＼）ｐＳｌＳ［ｉ］ｎ－ｌ＊＋ｂｐｌ＾＾ｒａ＾￡＾（）＾．￣ＣＣ〇ｔ■ｍａｘ－２ｍａｘｐ＾＾＼＼）／）Ｖｓ－ｓｒ＾ｓＢ＊ｉｉｅ［］＝ｉｌＡ６且６ｍ＿１算法２选择的机器数为，＜。结合ｎ＞ｍ可得ｗ－１＋＆（）＜１＾＜１＾＾＜２－－＋＋．ｎｎｎｍ根据１９７４年Ｈｏｒｏｗｉｔｚ等人［４０］给出背包问题的多项式时间近似方案（ＰＴＡＳ）的最坏情况界为１＋ｅ，可以类似得到ｓＥｉＥｓｗ＝ｉｌ因此２１＋、＾（士＋）□．１２ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究２５本．章小结工件长度是否相同两本章主要研宄云制造中带有固定租用成本的同类机调度问题，对２１种情况进行讨论。当工件长度不相同时，给出了最坏情况界为＋的近似算法。当（＆）工件长度相同时２ｌｅ１－，给出了最坏情况界为＋的近似算法。（））（告；１３ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究第３章带单位加工成本的同类机调度问题３１．引言本章主要研宄云制造环境下带单位时间加工成本的同类机调度问题。每台机一工速度和单位时间加工成本。云制造平台提供ｍ台机器器都有个加，机器集合＝１１一工速度为表示为抓７１。机器风的加如单位时间租用成本为１｛１，２，，４１｝从顾客那里获得的需要加工的＝ＪＪ…Ｊ工ｎ个工件，工件集合表示为Ｊ｛１，２，，？｝，＝１２．．．ｎ工速度为单位１的机器上进行加工的时间记为件々，放在加。这ｎ个工件，ｊ，，，巧都可以放在ｍ台机器上进行加工，且工件是可分的ｆｒａｃｔｉｏｎａｌ，其中工件可分表示工件在（）同一时刻可以在不同的机器上进行加工一些机器加工工件些机器的总加。制造商租用，这工成本记为制造商的总预算成本是固定常数＾目标是在不超过给定的总预算成本＾的情况下使得最大完工时间ｍａ／ｃｅｓｐａｎ最小。这个问题可以用符号Ｑｍ／ｒａｃ［／ｇＧＣｍａｘ（），｜ｌ表不。在云制造环境下，Ｌｉ等人４１研宄了带资源的平行机调度问题，文章的假设条件是机［］器带有单位时间加工成本，其目标函数也是极小化最大完工时间。给出了可中断情况下问题的一２的近似算法一个最优算法，但并未给出；给出了不可中断情况下最坏情况界为个紧的实例。本章对云制造资源调度问题的研宄，是把文献４１中的同型机调度问题推广到同类机［］一调度问题。对于工件长度不相同而且是可分的同类机情况，给出个最优算法。２３本章的具体内容安排如下：第部分给出了问题用到的符号定义部分给出了问；第（７的最优算法第４部分对全章进行概括总结。０ｍａｘ；３．２符号定义为了具体描述云制造资源同类机调度问题，引入以下符号：ｍ：云制造平台提供的的机器数量；ｎ：制造商需要加工的工件数量；＝抓…ＴｋＴ７１＾云制造平台提供的机器集合；｛，２，，＝？／《／制造商需要加工的工件集合｛九２；？：工＾／的长度巧件；，尸：ｎ个工件的总长度；机器风的加工速度，即单位时间加工的工件长度；Ｌ机器风的单位时间租用成本；１４ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究给定的总预算成本；机器加工工件需要的总成本；Ａ：机器风的负载；ｃｌｗ机器风的完工时间；：算法４的目标函数值ｍａ／ｃｅｓｐｃｍ）；（Ｃｍａｏ；（ｏｐｔ）：最优调度的ｍａ／ｃｅｓｐｃｍ。３．３Ｑｍ／ｒａｃ优算法｜，一工件在可分情况下的最优在这小节？Ｃ［／（７，我们研宄问题Ｑｍ／ｍａｘ，给出，Ｓ０｜工件都是可分的一时刻允许工件在不同的机器上加工算法。每个，即同。设ｎ个工件的工成本为＝．．．总长度为尸，机器风的速度为和，单位时间加丨，ｌ２ｍ。巧ｉＧ，，，）对机器的速度大小顺序没有要求…工，但是机器满足告ＳＳＳ机器风的完＊＊１２时间记为Ｃｌｒａ，１ｇｉｇｍ，则机器风的加工成本为，因此这ｍ台机器的总加工＝工时成本为［／￡ｃｌａ乂。目标是在不超过给定的总预算成本＾的情况下使得最大完＝１１间ｍａ／ｃｅ印ａｎ最小。（）若不考虑机器的加工成本，可以得到问题＜３爪介况，／７＜的松弛问题为Ｑｍ／ｒａｃＣｍａｘ，｜｜｜＝用（＾问题的最优解。，可以得到Ｃ＾｜＾表示这个ａｘＳＹｊｉ＝ｌｉ＇（（（（＜＞〇＾［／７＿为７＿｛〇为７〇＾７＿｛是对于问题９，设这个问题的最优解，因？１？？１１／，５＆｛辦）３／｜｜（｜｜？Ｃ［Ｚ（７问题Ｑｍ／ｍａｘ的松弛问题，故，Ｓ｜０＾〇ｐｔ＝＂ｍａｘ）＾＾ｍａｘｍ（＝ｉｌ＝２Ｃ我们首先解决当ｍ时的调度问题，即Ｑ２／ｒｃｉＣＬ／ｇＧｍａｘ。，｜｜假设Ｓ＾Ｓ在不超过给定的成本Ｇ的条件下可以找到问题的最优，解。根据前提条件＆Ｓ吾，易证Ｇａｘ２。如果Ｇａｘ＜，则可以把抓２中介于到这个时间段的工件截断放在机器抓１上加工，同时机器的加工成本不会增力口，因此工件的排序也是可行的。故可证ｃ＾Ｃ。ａｘ２＾ａｘ由此可以得到１＝Ｃ＾＋／２ＣＵ３．１ｈａｘ（）＊Ｃ＾Ｓ＋Ｃｓ＝？３．２ａｘｌ＾■ｉａｘ２（）１５ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究由式３．１和３．２联立可得（）（）Ｐｈ￣ＵＳｌ！＿＝ｍａｘｋｓ－ｉｈｓ２又因为Ｇａｘ２Ｇ，所以ａｘ八Ｐ—ｈＵｓｉｒ，！ｃｏｐｔ＝－—ｍａｘ）；｛Ｊｈｓ－ｉｈｓ２？Ｃ［／（７。根据上面的结论，给出算法来解决问题Ｑ２／，Ｓ＆ｍａｘ｜｜算法木一ｓｔｅ１■如果＾丨ｐ，则问题没有可行解，算法停止；如果吾ＫＧＳ吾２，则进行下步；＝＝ｓｔｅｐ２■如果，则（７ｍａｘ〇辦告告（）如果＜，则告１上加工＝８七６？３．把７１个工件以任意顺序放在机器７１４１，直至（＾＾（７？＾〇辦，若工件的加工（）时间超过Ｃ＾则把工件中断，将工件中断的部分和剩下的工件放在机器抓２上进行加ａｘ工。下面我们研宄当爪２３时的问题，在研宄问题的‘／７＾［／＜０（７＿｛的算法之前，先，｜一通过引理３．１说明问题最优调度中的些性质。工工件…．１３：台紙引理３当ｍ２时，设最优调度中选择Ａ机器加，即抓地，由，，，此可以得到最优解的一些性质如下：１－＝ｉＡ：１ＣＣ〇对于任意的１ＳＳ，有＾ｍａｘ辦）；ａｘ（（）Ｃ＇＜＇Ｃ〇ｐｔｍａｘ；（＾ｍａｘ（）３＝．．．＝如果Ａ：＜ｍ，则对任意的ｉ，ｉ／ｃ＋１ｍ，有０。（），，一？？？证明：因为＆ＳｇＳＳｔ，所以最优调度定是选择单位速度成本小的机一Ａ＝…＝４是最后台被选择的机器ｉｉ／ｃ＋ｌｍ有６０器。若，易知对任意的，，＾，（，，）＾则３得证。因为（７ｍａｘｏｐｔ是问题的最优解，因此Ｃ＾ａｘＳＣｍａｘｏｐｔ，那么２得证。下（）（）（）（）一１１Ａ－：１（７＜（７〇ｐｔ。此面开始证明性质，若存在台机器，ＳｇＳ，使得＾＾ｍａｘ％（）（）一工工件长度记为Ａ７１７１时，其中，可以在机器４上截取部分工件放在机器截取的ｐ＾上加，＝－Ｍ７Ｃ〇Ｃ。此中增加的费用为１使得ｍａｘ时机器，机器４中减少的费用辦）ａｘ￥（＾９￣￥为由５笋，可知所以调整之后机器的加工成本减少了，故总加工成关ｂ〇１〇ｑｑｋＧ１本不会超过，因此调整之后的排序还是可行的，则可证。（）引理得证。口１６ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究下面研宄当机器的总加工成本不超过＆时，最优调度中的机器的最大完工时间。根据弓．１丨理３中最优解的性质可以得到＇＇＇＝３＾Ｃ＋＾Ｃ＾Ｕ．３ｉｍａｘｍａｘ＾Ｃｍａｘ（）ＣＣ＝＋ｓＨ卜ｓｋＰ３－４２＾ａｘ＾ａｘ（）又因为＝Ｃ＝…＝Ｃ３Ｃｍａｘｍ．５ａｘｍａｘ（）由式３．４和３．５联立可得（）（）－Ｐ￣＾ｇＳ＋办＿ｍａｘｌ２＼ｈ１ｋ＿（）ｆｊ３６（）ｓｋ由式３．３３．５３．６，和联立可得（）（）（）Ｐ／—ＵＳａＡ１：ｋ—广＿￣￣——Ｃｍ°Ｐｔ＾■ａｘ）ｍａｘ｛＿ｌｉｉ＝ｌｉ＝ｌ一上界为Ｆ因为Ｇ是个限制条件，，，，我们需要确定Ｇ的范围令Ｇ的下界为Ｅ那么辽５疗。如果辽，则问题不可行；如果［／２Ｆ，则给定的预算成本对问题的调度没＝疗有影响，那么令［／。ｍ＝上界为尸３．２。定理给定的预算成本＆的下界为２＾。，Ｓ２＾ｉ１证明：如果把所有的工件都放在单位速度成本最小的机器Ｉ加工，则可以得到总加工成本Ｇ的下界．．．。因为工件放在机器上加工ｆＳｆＳＳ饫，所以把所有，可以得＊１＊２＝工工件工件的加到Ｇ的下界为泛ｆＬ。接着考虑成本的上界，如果选择ｍ台机器加，则６１工成本最大。此时得到Ｐｃｏｐｔ＝－―ｍａｘ（）＾＝ｉｌ因此加工成本的上界为ｍＺ］ｋｕ＝ｉ＾—ｐ１ｕ１ｍｉ＝ｌ１７ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究定理得证。口根据上面的过程，设计算法来解决问题＜９ｍ／？Ｃ，［／＜ＵＣｍ＾〇｜＼算法４ｓｔｅｐ１．根据定理３．２算出辽和！７，如果则问题没有可行性调度，算法停止；如＝果＾＞！７，则令＾＂ｓｔｅ２．＝丨／＝１＝丨＝ｐ如果０辽，贝Ｊｃ；如果Ｇ［／，贝Ｊ／ｃｍ；＝如果辽＜＾＜！７ＩｉＧ，贝ＪＡ：ａｒｍｎｇｔＪｆ；ｆ：ｐ｝Ｅ？＝ｉｓｉ＝ｌｉｓｔｅ３■＝（７ｏｐｉ＝ｐ如果，则ｍａｘ告告（）Ｅｓｉ＝ｌｉＰ￣ｌＵｓＣ＝＾ｋｋ如果告＜，则ｍａｘ（〇辦）ｍａｘ｛ｉ，ｋ１ｋ＿１｝；ｉｓｓ￣ｓｌｉｉｋｉ＝ｌ＝ｌ＝ｌｉｉｉ４Ｍ．．．ｓｔｅ．把ｎ个工件以任意顺序从０时刻开始放在机器抓上进行加工ｐ，使，ｓ，，＝＝—…工得Ｃ＜〇丨１２Ａ：１。（７ｌ＿，如果工件加工时间超过＿辦，则把ａ；ｃ＾辦），，，（＞）一－１件中断，剩余的部分放在下台机器上加工，当前Ａ台机器的调度完成时，则把剩余的工件放在机器７１４上加工。定理３．３Ａ得到问题的ＱｍｒａＣ［／（７最优解。算法４／，ｇ０ｍａｘ｜＝＝＝证明：根据算法厶的对ｅｐｌ和ｓ鄉２可知，如果＾辽，贝仪１；如果＾疗，ｌ＝贝｜ｆｃｍ，显然此时可以得到问题的最优排序。若则选择的机器数目为Ａ：，根据ｓｔｅｐ３可得ｍＰ＾ｋ＝ａｒｇｍｉｎ——ｈ＞Ｕｊ｝ｈ２＿＾１＝ｉ１ＳＴｉ．＝ｉｌ由于优先选择单位速度加工成本较小的机器，因此选择的Ａ：台机器满足ｈｈｌｋ，ｚｚ＾＾１２工得到最优排序。如果存在机下面证明如果把ｎ个工件放在选择的Ａ：台机器上加１且。７１器７４和％，满足ｇＳ￥，？Ｓ％按照算法丰应该先选择机器４加工工件，但是因为知＜如果我们先选择速度大的机器进行加工７１，即把机器４和选择的顺序交换。下面验证在机器的最大完工时间不变的情况下，我们交换顺序时候机７？１〇器的总加工成本是否减少。设交换顺序之前机器４加工的工件长度为Ｃｍａｘ（辦）＆，机１８ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究＿〇？工的工件总长度是保持不器加工的工件长度为Ｃｍａｘ辦？，因为两台机器加（）（％）工的工件长度为？变的０（７〇ｐｔ。，那么交换顺序之后机器Ｉ的负载为，机器加ｍａｘ巧（）假设交换顺序之后机器的加工成本不减少，则应该满足￣Ｃ〇Ｐｔ＇ＳＳｍ＾ｘｉ）｛ｙ）■Ｃｍａｘｏｐｔｌｘ＋ｌ＜Ｃｍａｘｏｐｔｌ（）ｙ（）ｙｓｙ化简之后可得＿ｌｌｘ８＋ｌ８Ｓｘｙｙｙｙ＾＾〈ｓｙ即ｌｘ８〈ｌ８ｘｙｙ因此——＜■３８ｘｙ满足之前的前提条件，故假设成立，即交换机器顺序之后机器的总加工成本不会减少，因此算法Ａ４是问题Ｑｍ／ｒａｃ，／７ｓ的最优算法。｜定理得证。口３．４本章小结本章主要研宄云制造环境下带有单位时间加工成本的同类机调度问题，目标是极小化最大机器完工时间＜？？？且工件是可分的情况。对于机器满足，＾＿＆＜＜而给出了问６１６２〇ｍ题的最优算法。１９ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究第４章带单位加工成本的同型机覆盖问题４１．引言本章主要研宄云制造环境下带有单位时间加工成本的同型机调度问题。每台机器都＿一工成本＝。云制造平台提供ｍ台机器ＴｋＴ７Ｗ有个单位时间加，用集合ｍ表，｝示。机器风的单位时间租用成本为Ｉ制造商从顾客那里获得需要加工的ｎ个工件，用＝？Ｊ．．．表示工速度为单位１的机器上进行加工所用的时集合Ｊ义２，工件放在加｛，，，４＝ｌ２．．．ｎ工件都可以放在ｍ台机器上进行加工间记为巧，ｊ。这ｎ，且工件是可中断，，，个的。机器风的完工时间记为Ｃｌａ，１ｇｉｇｍ，那么机器风的加工成本为ＣＵ，因此；ｃ／＝ｃ／这ｍ台机器的总加工成本为ｔ这些机器的总加工成本记为［。制造商的加工；￡ｌａｘＬｉ＝ｌ成本预算资源是固定常数Ｇ，ｆ标是在不超过给定的总预算成本Ｇ的情况下，使机器的（）＿最小完工时间最大（７，即机器覆盖问题。为了方便表述，用符号尸？？７＾７１［／＾０表？＾７１来／，｜｜示本章所要研宄的问题。关于云制造资源调度问题的文献大量存在，然而目前还没有文献考虑云制造资源机器一覆盖问题，本章是把文献４１中极小化最大完工时间ｍａｋｅｓｐａｎ这问题扩展到极大化最［］（）一些结论小完工时间的调度问题，并得到。本章内容安排：第２部分给出了问题用到的符号定义；第３部分给出问题Ｐｍｐｍｔｎ（７ｍｉｎ的｜｜最优算法；第４部分对全章进行概括。４．２符号定义为了具体描述云制造资源同型机调度问题，引入以下符号：ｍ：云制造平台提供的的机器数量；ｎ：制造商需要加工的工件数量；＝…ＴｋＴ７Ｗ从地：云制造平台提供的机器集合；｛，，，ｍ｝＝…？／《／２：制造商需要加工的工件集合九；｛，，人｝工件？＾：／的长度巧；，尸：ｎ个工件的总长度；ｎ个工件中最大的工件长度；Ｌ机器风的单位时间租用成本；给定的总预算成本；机器加工工件需要的总成本；机器风的完工时间；２０ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究算法４的目标函数值机器覆盖；（）Ｃｍｉｎ〇辦：最优调度的最小机器完工时间。（）４．３最优算法一＾？在这小节，我们将给出尸？１７［／（７的可中断情况下的最优算法。７１个工卜，５０？＾…工成本记为Ｉ＝－．ｍ。〗１２件的长度满足ＰｉＳＰ２ＳＳ？机器风的单位时间加，，，，一一且满足Ｌ．．．Ｓ丨２ＳＳ。这ｎ个工件都可以放在ｍ台机器上进行加工，台机器同一一一时刻只能加工工件工件同一个，个时刻只能放在台机器上加工。机器风的完工时间记为１ｇｉｇｍ，那么机器风的加工成本为（７％，因此ｍ台机器的总加工成本记＝为［／（７％在不超过给定的总预算成本Ｇ的情况下使得机器最小完工时间最￡，目标是＝２１大。若不考虑机器的加工成本，得到问题仏＿加，ＵＳＧＣｍｉｒｉ的松她问题为仏＿糾Ｃｍｉｎ，｜ｌ｜用表示松弛问题的最优解，可以得到ｎ—ｊＥＰｉＣ＝ｍｉｎｍ＿ｊ（７ｏｐｔ为是对于问题，设这个问题的最优解为ｍｎ，因ｉ（）问题ｓ的松她问题，故ｎ－ｊＴｉ，Ｐ＝２ｍｔｎ我们首先解决ｍ的调度问题，即巧ｐ［／ｓ，｜如果不考虑机器加工成本？７１加（７，可以得到问题巧／？＾的最优解为｜｜＾＝ｍｉｎＰ－ｍａｘｍ＞Ｐｉｎｆ｛｜把ｎ个工件放在机器７１＾和抓２上进行加工，因为加工时优先选择单位时间加工成本较低的１２７１丨（７。机器，又ｉＳＧ，所以优先把工件放在机器＾上进行加工，因此Ｃ２如果＊Ｐ－Ｃ＋ｃ＜ｌＪｋｌ２ｕ（ｍｎ，ｉ则＾〇Ｐｔ＝Ｃ＝ｍｉｎ＿ｍｉｎｍＰｍａｘ］｛）ｉｎ＾２１ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究如果Ｐ－Ｃ＋Ｃ＞ｕｌｉｎ）ｋＩＪ２，（当匕＾匕时，令１Ｃ＼Ｐ－Ｃｈ＝ｕ＋，（）化简可得Ｐ＾－ｕｉｒ—，ｈ－ｈｈ—ｎＣ２由〇可得八２Ｃｏｐｔ＝Ｃ＝—－ｍｉｎ（）ｐｈ—ｈ根据上面的过程设计算法解决问题即尸２ｐｍ加，ＵＳ｜算法４一１ＰｌＰｌｓｔｅ．有可行性排序如果Ｌ，算法停止如果＾２，ｊ进行ｐ，贝ｊ问题没；Ｌ贝下步；＝＝３－ｓｔｅ２■如果ＬＺ２，则（７ｍｉｎｏｐｉｍｉｎｉｐｐｍａｘ，；（）｛昏｝３＝ｉｉ－１＞如果丨ｉ＜丨２，则ＣＵｏｐｉｍｎｍａｘ；ｉｎｐ，，（）ｆ令等｛ｊｓｔｅｐ３．把ｎ个工件按照长度从大到小的顺序放在机器从上从０时亥［Ｊ开始加工，使得１＝工件中断＜＾（７（７＿辦，若工件的完工时间超过，则把；＞）ｓｔｅｐ４．把从机器］＼＾上中断的工件从０时刻开始放在Ｍ２上加工，剩余的工件按照长度从大到小的顺序继续放在机器Ｍ２加工。定理４．１算法是问题尸２卜爪加，［／ｇ的最优算法。下面我们开始研宄ｍ２３的问题。．．．且满足根据已知条件可知仍ｇＰＳＳｎ。如果ｍａｘＳ，２ＰＰ￡ｍｐ－ｋ＜ｕＹ，，＝则Ｃｏａｄｏｐｔ；如果ｐｍａｘ＞，若是不考虑机器的加工成本得到问题的）吾吾２２ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究最优解为ｎ－ｊＴ，ＰｉＣ＝ｍｉｎ—￣＾：ｉｎ—０＜ｊ＜ｍ－ｌｍＪ令ｎ—ｊ＝ａｒｇｉｎ４．１７ｍ（）ｊ＝〇ｍ－ｊｎ—７ＥＰｉ＿Ｐ＝＾—４．２（）ｍ—７？…工件＾＾上放在机器上加工《／放在机此时把工件人放在机器加工，工件人－ｉ，，？＿７＋１－工件以任意顺序放在剩下的ｍ－台机器上加工器上加工，然后把剩余的ｎ７个７。由此可以得到，当１ＳｉＳ７时机器风的完工时间为＝４．３ｐｎ＋ｉ－ｉ（）当７＋１ＳｉＳｍ时，机器风的完工时间为Ｐ。下面开始考虑机器受加工成本限制的问题，如果２．．．Ｐ．．．＋（７＜＋＋＋＿Ｚ＋Ｚ＋＋ＳＧ２（７＋ｉ７＋２则可以得到问题的最优解为ｎ—７ＥＰｉＣ〇Ｐｔ＝——ｍｎｉ（）ｍ—７如果２．．．．．．＋（＾，＋＋＋Ｐ２＿Ｚ１＋Ｚ２＋＋Ｚｍ＞（）＋）＋）一．．．７则在机器抓财抓１２中各截取相同长度的部分工件放在机器＾上加工。设机，３，，７＝０－器风２ｉ？。那么此时机器７１＾的完工时间，ｇｇ７截取的工件长度为１＾Ｍ．．．为（７＋ＡＣ，机器ｓ竭的完工时间为户。ｆ：，，，＝ｉ２如果７ｍ＝ｉ＝ｉ２２则可以得到问题的最优解为７１—７ＥＰｉＣ〇ｐｔ＝——ｍｉｎ；［）ｍ—７２３ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究如果７ｍｃ１ＡＣ＋＋ｐｌ＞＾％ｉ（ｊ２Ｊ２＝＝ｉ２ｉ２一ＭＭ．．．Ｍ７则继续在机器部分工件放在机器１＾上加工２ｍ中各。设截，２，，截取相同长度的５取的工件长度为，令＿＂７１ｍ１－Ｐ－＝（７＋＋ｍ１６ｈ６ｌＵ（）＋（）ｉ＾Ｊ２＝＝＿ｉ２Ｊｉ２化简可得入＼ｍ（７＿，ｌｉＵ－ＣＡＣ－Ｐ＋ｈＺＹｌｋ（）＝＾＾＾Ｓ－４（４）ｍ—１—ｌｌｉ＾ｉ（）＝ｉ２那么问题的最优解为＝Ｐ－４Ｃｍ？〇ｔＳ．５ｉ（ｐ）（）联立式４．２４．３４．４和４．５可得（），（），（）（）Ｎ１，ｉＰ－ｌ－）＋ｍｈｔｆ（７＋ＡＣｈ（）ｆ：）Ｃｏｐｔ＝￣￣—ｍＵ）—１—ｍｌｌｉ＾ｉ（）ｉ＝２由上面的过程我们给出算法Ａ；来解决问题尸ｇ算法Ａ；ｎ－ｊ１２Ｐｉ＝ｓｔｅｐ１．根据问题得到问题的最优解为Ｃｍｉｎｒｚｒ％＾ｉｎ＾—Ｊ０＜ｊ＜ｍ１ｎ—ｎ—７ｊＥＰｉＥＰｉ＿＝ａｒｉ■尸＝取ｇｍｎ，７ｆ０；＝＾＾２．．．工件Ｊｓｔｅ．７１７Ｗ上加工放ｐ先把工件人放在机器＾上加工，工件放在机器２，，？＿７＋１在机器抓上加工－工件以任意顺序放在剩下的ｍ－，然后把剩余的ｎ个台机器上７７７加工；一ｓｔｅ３．１ｉ工时间为〇＝ｐ根据上步可得当ｇｇ７时，机器风的完Ｐｎ＋ｉ－；ｉ当１ＳｉＳｍ时，机器风的完工时间为Ｐ７＋；２．．．．．．ｓｔｅ４■（７，ＺＺＧｐ如果＋２＋＋＋＿Ｐｉ＋Ｚ２＋＋ｍＳ，（７＋７＋）２４ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究ｎ—７ＥＰｉ＝ｉ贝ｊ可以得到问题的最优解为；＾．．．．．．．．．抓ｓｔｅ５■如果Ｚ＋Ｚ＋＋＞匕则在ｐＣ％＋Ｃ％＋＋Ｃ＾＋Ｐ１２机器地中７（７＋７＋Ｕ，竭，，７一２各截取相同长度的部分工件放在机器上加工，ｉ。设机器风＾＾７截取＾１＝－７０Ｐ。１的工件长度为ＡＣ那么此时机器＾的完工时间为（７＋ｆ，机：ｉ＝２…的完工时间为Ｐ器地；，地，，ｎ—７７ｍＪ２Ｐｉ—１＊＝ｓｔｅｐ６■如果（７＋Ａ（７／ｉ＋Ｐｙ＾ｈＳＲ则可以得到问题的最优解为；（亡）二＝＝ｉ２ｉ２１７＾７＾．．．７８七６１７．如果（＾＋（＾＋？交＞＆＾中各截取相同长，贝｜继续在机器２？％，２，，（；＾＞＾＝＝ｉ２ｉ２Ｕ－ｆｃ＾Ｊ：ＡＣｈ－Ｐｈ＾ＥＶ＝２《５＝￣￣￣￣＾工件放在机器恥上加工度为４，此时得到问题的最优解为２ｌｉ＝２ｉＰｍ－－Ｕ＋ｆ＾＋ＡＣ＾ｈｉ＾ｈｉＣ〇ｐｔ＝￣—〇ｍｉｎ（）ｍ－ｌｈ－ｋ（）Ｘ）＝２ｉ定理４．２算法Ａ是问题尸ｇ的最优算法。；４．４本章小结本章主要研宄云制造资源中带有单位时间加工成本的同型机调度问题，目标是极大化最小完工时间一工成本工件都是可（机器覆盖）。每台机器都有个单位时间加，对于每个中断的情况。本章给出２台机和ｍ台机的最优算法。２５ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究第５章总结与展望本文主要研宄了三类云制造资源调度问题。第一类问题为带有固定加工成本的云制造资源的同类机调度问题，目标为极小化最大工时间工件是不可中断的一完。文章对已有文献的相关结果分为两种情况进行了更般化，的研宄。分别给出了问题的近似算法和最坏情况界，但是目前还没有找到问题的最优算一法，需要进步研宄。第二类问题为带有单位时间加工成本的云制造资源的同类机调度问题，目标为极小化最大完工时间。本文是在已有文献的基础上进行研宄，把固定加工成本推广到单位时间加工成本，并且把云制造资源同型机调度问题扩展到到同类机的调度问题。研宄了工件可分一些需要改进的地方是情况下的调度问题，在云制造资源，给出了解决问题的最优算法。单位成本调度问题中，对于工件不可分的情况，即目前还没能找到最优一。算法，这将是下步需要研宄的方向第三类问题为云制造资源的同型机覆盖问题。本文我们研宄的是云制造环境下带有单位时间加工成本的机器覆盖问题，比经典机器覆盖问题更有难度，所以本文只考虑了工件可中断的情况。参考经典排序问题算法的思路和已有的云制造调度问题文章中的算法，给出了问题可中断情况下最优算法。接下来可以研宄带有单位时间加工成本的同类机机器覆７？加［／（７＿的近似算法或最优算法盖问题，即９？５，也可以研宄不可中断情况下的＞，０同类机或同型机覆盖问题，即ｓｓ２６ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究参考文献１ＧｒａｈａｍＲＬＬａｗｌｅｒＥＬＬｅｎｓｔｒａＪＫｅｔａｌ．ＯｔｉｍｉｚａｔｉｏｎａｎｄＡｒｏｘｉｍａｔｉｏｎｉｎ，，，ｐｐｐ［］ＤｅｔｅｒｍｉｎｉｓｔｉｃＳｅｕｅｎｃｉｎａｎｄＳｃｈｅｄｕｌｉｎ．Ｍａｔｈｅｍａｔｉｃｓｑｇ：ＡＳｕｒｖｅＪＡｎｎａｌｓｏｆＤｉｓｃｒｅｔｅｇｙ，［］１９５ｌ２８７－３２６７９．：，（）２ＭｉｃｈａｅｌＰｉｎｅｄｏ．调度：原理、算法和系统Ｍ．北京：清华大学出版社２００７．，［］［］－３．．Ｄ．蒋义伟浙江：浙江大学博士学位论文２００７：１１１８可中断平行机排序问题研究，［］［］一４－．．Ｄ２００６ｌ２８．黄宜坤定条件下平行机排序问题的研究浙江：浙江大学硕士学位论文：，［］［］５ＬａｎｓｔｏｎＭＡ－－ｇ．Ｉｎｔｅｒｓｔａｇｅｔｒａｎｓｐｏｒｔａｔｉｏｎｐｌａｎｎｉｎｇｉｎｔｈｅｄｅｔｅｒｍｉｎｉｓｔｉｃｆｌｏｗｓｈｏｐｅｎｖｉ［］ｒｏｎｍｅｎｔＭ．ＩＮＦＯＲＭＳ１９８７．，［］６ＧｒａｈａｍＲＬ．ＢｏｕｎｄｓｆｏｒＣｅｒｔａｉｎＭｕｌｔｉｐｒｏｃｅｓｓｏｒＴｉｍｉｎｇＡｎｏｍａｌｉｅｓＪ．ＢｅｌｌＳｙｓｔｅｍ［］［］Ｔ－ｅｃｈｎｉｃａｌＪｏｕｒｎａｌ４５：１５６３１５８１１９６６．，，７ＧｒａｈａｍＲＬ．ＢｏｕｎｄｓｏｎＭｕｌｔｉｐｒｏｃｅｓｓｉｎｇＴｉｍｉｎＡｎｏｍａｌｉｅｓＪ■ＳｉａｍＪｏｕｒｎａｌｏｎＡｌｉｅｄｇｐｐ［］［］Ｍａｅｍａｉｃｓ１９６９１２４１６－４２９ｔｈｔ７．：，，（）ＰｉＫ－－８ｒｅｓｓ．ＡｉｌｅｍａｎｕｆａｃｔｕｒｉＪ．ＣｏｍｕｔｅｒＡｉｄｅｄＤｅｓｉ１９９４２６２．ｇｎｇｐｇｎ：８３８４，，［］［］（）９ＹｕｓｕｆＹＹＳａｒｈａｄｉＭＧｕｎａｓｅｋａｒａｎＡ．Ａｉｌｅｍａｎｕｆａｃｔｕｒｉｎ：Ｔｈｅｄｒｉｖｅｒｓｃｏｎｃｅｔｓａｎｄ，，ｇｇ，ｐ［］－ａｔｔｉｂｔｅｓ－ｒｕＪ．ＩｔｅｒｔｉｏｌＪｏｕｒｎａｌｏｆＰｒｏｄｕｃｔｉｏｎＥｃｏｎｏｍｉｃｓ１９９９６２１２３３４３．ｎｎａｎａ：，，［］（）ＴａｏＦＨｕＹＦＺｈｏｕＺＤ－１０．Ｓｔｕｄｏｎｍａｎｕｆａｃｔｕｒｉｎｒｉｄａｎｄｉｔｓｒｅｓｏｕｒｃｅｓｅｒｖｉｃｅｏｔｉｍａｌ，，ｙｇｇｐ［］ｓｅｅｃｔｉｏｎｓｓｔｅ．ＩｔｅｒｔｉｏＡｃｅｃｔｕｒｉｎＴｅｃｈｎｏｌｏ２００８ｌｙｍＪｎｎａｎａｌＪｏｕｒｎａｌｏｆｄｖａｎｄＭａｎｕｆａｇｇｙ，，［］－－４３７９１０．：１０２２１０１（）１１ＦａｎＹＺｈａｏＤＺｈａｎＬ－ｅｔａｌ．ＭａｎｕｆａｃｔｕｒｉＧｒｉｄｉｎ：ＮｅｅｄｓＣｏｎｃｅｔａｎｄＡｒｃｈｔｅｃ，，ｇ，ｇ，ｐ，［］ｔｕｒｅＣＧｒｉｄａｎｄＣｏｏｐｅｒａｔｉｖｅＣｏｍｐｕｔｉｎｇＳｅｃｏｎｄＩｎｔｅｒｎａｔｉｏｎａｌＷｏｒｋｓｈｏＧｃｃ２００３，ｐ，，［］／／ｉＤ－－ＳｈａｎｈａＣｈｉｎａｅｃｅｍｂｅｒ７１０２００３ＲｅｖｉｓｅｄＰａｅｒｓ．ＤＢＬＰ２００３．ｇ：６５３６５６，，，，ｐ，１２李伯虎张霖王时龙等．云制造：面向服务的网络化制造新模式Ｊ．计算机集成制造系，，，［］［］２０１０１６１１－统．：７，，（）１３－．２０１１１７３４４９４５７．李伯虎张霖磊再论云制造计算机集成制造系统：，，任，等，，［］（）２７ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究１４李伯虎赵欣培张霖等．云制造制造领域中的云计算Ｃ中国化工学会信息技术应，，，［］［］／／用专业委员会年会．２０１１．１５李伯虎张霖任磊等．云制造典型特征、关键技术与应用系，，，［］见计算机集成制造２０１２１８１３４５－１３５６７．统：，，（）１６肖莹萤．云制造中的制造能力服务形式化描述方法Ｊ．系统仿真学，李伯虎，柴旭东，等［］［］２０１５２７９２０９６－２１０７．报：，，（）１７李伯虎柴旭东张霖等．智慧云制造：工业云的智造模式和手段⑷．中国工业评论，，，，［］－２０１６Ｚｌ．：５８６６（）［１８］ＮｏｇａＪ．ＳｃｈｅｄｕｌｉｎｇｗｉｔｈＭａｃｈｉｎｅＣｏｓｔ［Ｃ］／／ＩｎｔｅｒｎａｔｉｏｎａｌＷｏｒｋｓｈｏｐｏｎＡｐｐｒｏｘｉｍａｔｉｏｎＡｌｇｏｒｉｔｈｍｓｆｏｒＣｏｍｂｉｎａｔｏｒｉａｌＯｐｔｉｍｉｚａｔｉｏｎＰｒｏｂｌｅｍｓ：ＲａｎｄｏｍｉｚａｔｉｏｎＡｐｐｒｏｘｉｍａｔｉｏｎ，，ｉｉｉＴｉ－－ａｎｄＣｏｍｂａｌＡｌｏｒｔｈｍｓａｎｄｅｃｈｎｕｅｓ．ＳｒｉｅｒＶｅｒｌａ１９９９１６８１．ｎａｔｏｒｇｑｐｎｇｇ：７６，１９ＩｍｒｅｈＣ．ＯｎｌｉｎｅｓｃｈｅｄｕｌｉｎｇｗｉｔｈｅｎｅｒａｌｍａｃｈｉｎｅｃｏｓｔｆｕｎｃｔｉｏｎｓＭ．ＥｌｓｅｖｉｅｒＳｃｉｅｎｃｅ［］ｇ［］ＰｕｂｌｉｓｈｅｒｓＢ．Ｖ．２００９．［２０］ＪｉａｎｇＹ，ＨｅＹ．Ｐｒｅｅｍｐｔｉｖｅｏｎｌｉｎｅａｌｇｏｒｉｔｈｍｓｆｏｒｓｃｈｅｄｕｌｉｎｇｗｉｔｈｍａｃｈｉｎｅｃｏｓｔ．［Ｊ］．ＡｃｔａＩｆｏｒｔｉｃａ２００６２１６９８４－９８８．ｎｍａ：，，（）２１ＤｏｓａＧＴａｎＺ．ＮｅｗｕｅｒａｎｄｌｏｗｅｒｂｏｕｎｄｓｆｏｒｏｎｌｉｎｅｓｃｈｅｄｕｌｉｎｗｉｔｈｍａｃｈｉｎｅｃｏｓｔＪ．，ｐｐｇ［］［］Ｄｉｉｉｉ２０１０３１２５－１３５ｓｃｒｅｔｅＯｔｚａｔｏｎ７．ｐｍ：，，（）２２ｉａＹＨｕＬｉｕＬｅｔａｌ－ＪｎｇＪ．Ｃｏｍｅｔｉｔｉｖｅｒａｔｉｏｓｆｏｒｒｅｅｍｔｉｖｅａｎｄｎｏｎｒｅｅｍｔｉｖｅ，，，ｐｐｐｐｐ［］ｏｎｌｉｎｅｓｃｈｅｄｕｌｉｎｇｗｉｔｈｎｏｎｄｅｃｒｅａｓｉｎｇｃｏｎｃａｖｅｍａｃｈｉｎｅｃｏｓｔＪ．ＩｎｆｏｒｍａｔｉｏｎＳｃｉｅｎｃｅｓ，［］２０１４２６９１１１２８－１４１．：，（）２３ＲｕｓｔｏｇｉＫＳｔｒｕｓｅｖｉｃｈＶＡ．ＰａｒａｌｌｅｌＭａｃｈｉｎｅＳｃｈｅｄｕｌｉｎｇ：ＩｍｐａｃｔｏｆＡｄｄｉｎｇＥｘｔｒａ，［］Ｍａｉ－ｃｈＪ．ＯｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈ２０１３６１５１２４３１２５．ｎｅｓｐ：７，，［］（）ＹＹ－２４ＪｉａｎｇＨｅ．ＳｅｍｉＯｎｌｉｎｅＡｌｇｏｒｉｔｈｍｓｆｏｒＳｃｈｅｄｕｌｉｎｇｗｉｔｈＭａｃｈｉｎｅＣｏｓｔＪ．Ｊｏｕｒｎａｌ，［］［］ｉ４－ｏｆＣｏｍｕｔｅｒＳｃｅｎｃｅａｎｄｓｔｅｃｈｎｏｌｏ２００６６．ｐｇｙ：９８９８８，（）２５ＨｅＣＬｅｕｎＹＴＬｅｅＫｅｔａｌ．Ｓｃｈｅｄｕｌｉｎａｓｉｎｌｅｍａｃｈｉｎｅｗｉｔｈａｒａｌｌｅｌｂａｔｃｈｉｎｔｏ，ｇ，，ｇｇｐｇ［］ｍｉｎｉｍｉｚｅｍａｋｅｓｐａｎａｎｄｔｏｔａｌｒｅｅｃｔｉｏｎｃｏｓｔＪ．ＤｉｓｃｒｅｔｅＡｌｉｅｄＭａｔｈｅｍａｔｉｃｓ２０１６ｊｐｐ，，［］－２０４Ｃ．：１５０１６３（）２８ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究？２６ＥｌｖｉｋｉｓＤＨａｍａｃｈｅｒＨＷＴＫｉｎｄｔＶ．Ｓｃｈｅｄｕｌｉｎｇｔｗｏａｇｅｎｔｓｏｎｕｎｉｆｏｒｍａｒａｌｌｅｌ，，ｐ［］ｉｓｉｔｈｓａｎａｎｄｃｏｓｔｆｕｎｃｔｉｏｎｓ－ｗＪ．ＪｏｕｒｎａｌｏｆＳｃｈｅｄｕｌｉ２０１１１４５４７１ｍａｃｈｎｅｍａｋｅｐｎｇ：，，［］（）４８１．２７ＬＫＬＹＴｉＨ－？ｅｅｅｕｎＪａＺｅｔａｌ．Ｆａｓｔａｒｏｘｉｍａｔｉｏｎａｌｏｒｉｔｈｍｓｆｏｒｂｉｃｒｉｔｅｒｉａｓｃｈｅｄｕｌ，ｇ，，ｐｐｇ［］ｉｎｇｗｉｔｈｍａｃｈｉｎｅａｓｓｉｇｎｍｅｎｔｃｏｓｔｓＪ．ＥｕｒｏｐｅａｎＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ２０１４，，［］２３８ｌ５４－６４．：（）２８ＧｕｐｔａＤＳｈａｒｍａＳＳｈａｒｍａＳ．ＭｕｌｔｉｓｔａｇｅＢｉｃｒｉｔｅｒｉａＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍｓ：Ｍｉｎｉｍｉｚｉｎｇ，，［］ＲｅｎｔａｌＣｏｓｔｗｉｔｈＭｉｎｉｍｕｍＭａｋｅｓｐａｎＪ．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＯｐｅｒａｔｉｏｎａｌＲｅｓｅａｒｃｈ［］ａｎｄＯｐｔｉｍｉｚａｔｉｏｎ２０１２．，２９ＬｉＺＹａｎＨＺｈａｎＳｅｔａｌ．Ｕｎｒｅｌａｔｅｄａｒａｌｌｅｌｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｗｉｔｈｅｎｅｒ，ｇ，ｇ，ｐｇｐｇｙ［］ａｎｄｔａｒｄｉｎｅｓｓｃｏｓｔＪ．ＩｎｔｅｒｎａｔｉｏｎａｌＪｏｕｒｎａｌｏｆＡｄｖａｎｃｅｄＭａｎｕｆａｃｔｕｒｉｎｇＴｅｃｈｎｏｌｏｇｙ，［］２０１６８４１－４１－１４．：，（）３０ＤｅｕｅｒｍｅｙｅｒＢＬＦｒｉｅｓｅｎＤＫＬａｎｇｓｔｏｎＭＡ．ＳｃｈｅｄｕｌｉｎｇｔｏＭａｘｉｍｉｚｅｔｈｅＭｉｎｉｍｕｍ，，［］ＰｒｏｃｅｓｓｏｒＦｉｎｉｓｈＴｉｍｅｉｎａＭｕｌｔｉｐｒｏｃｅｓｓｏｒＳｙｓｔｅｍＪ．ＳｉａｍＪｏｕｒｎａｌｏｎＡｌｇｅｂｒａｉｃａｎｄ［］ＤｉｓｃＭｅｏｄｓ２００６３２１９０－１９６ｒｅｔｅｔｈ．：，，（）ｉＫ－３１ＷｏｅｇｎｇｅｒＧ．ＴｈｅｅｘａｃｔＬＰＴｂｏｕｎｄｆｏｒｍａｘｉｍｉｚｉｎｇｔｈｅｍｉｎｉｍｕｍｃｏｍｐｌｅｔｉｏｎｔｉｍｅ［］－Ｊ．ＯｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈＬｅｔｔｅｒｓ１９９２ｌｌ５２８１２８７．ｐ：，，［］（）３２ｅｉ－ＷｏｇｎｇｅｒＧＪ．Ａｏｌｎｏｍｉａｌｔｉｍｅａｒｏｘｉｍａｔｉｏｎｓｃｈｅｍｅｆｏｒｍａｘｉｍｉｚｉｎｇｔｈｅｍｉｎｉｍｕｍｐｙｐｐ［］ｉｉｉ－ｌｅｔｏｎｔＪ．ＯｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈＬｅｔｔｅｒｓ１９９７２０４４９４．ｍａｃｈｎｅｃｏｍｐｍｅｐ：１１５，，［］（）３３ＪｉａｎＹＴａｎＺＨｅＹ．ＰｒｅｅｍｔｉｖｅＭａｃｈｉｎｅＣｏｖｅｒｉｎｏｎＰａｒａｌｌｅｌＭａｃｈｉｎｅｓＪ．Ｊｏｕｒｎａｌ［］ｇ，，ｐｇ［］ｏｆＣｏｍｂｉｎａｔｏｉａｌＯｔｉｉｔｉｏ２００５１０４３４５－３６３ｒｚａ．ｐｍｎ：，，（）ＹＹ－３４ＨｅＪｉａｎ．Ｏｔｉｍａｌｓｅｍｉｏｎｌｉｎｅｒｅｅｍｔｉｖｅａｌｏｒｉｔｈｍｓｆｏｒｍａｃｈｉｎｅｃｏｖｅｒｉｎｏｎｔｗｏ，ｇｐｐｐｇｇ［］ｉｉ－ｕｎｆｏｒｍｍａｃｈＪ．ＴｈｅｏｒｅｔｉｃａｌＣｏｍｕｔｅｒＳｃｉｅｎｃｅ２００５３３９２２９３３１４．ｎｅｓｐ：，，［］（）３５ＣａｏＳＴＺ．ＯｎｌｉｎｅｕｎｉｆｏｒｍｍａｃｈｉｎｅｃｏｖｅｒｉｎｇｗｉｔｈｔｈｅｋｎｏｗｎｌａｒｅｓｔｓｉｚｅＪ．Ｐｒｏｒｅｓｓｇｇ［］［］ｉｎＮａｔｕｒａｌＳｃｉｅｎｃｅ：ＭａｔｅｒｉａｌｓＩｎｔｅｒｎａｔｉｏｎａｌ自然科学进展：国际材料英文２００７（（）），，１１１１２１－１２７．：７７８（）ＴａｎＺＹ－３６ＣａｏＳＪ．ＳｅｍｉｏｎｌｉｎｅＭａｃｈｉｎｅＣｏｖｅｒｉｎｏｎＴｗｏＵｎｉｆｏｒｍＭａｃｈｉｎｅｓｗｉｔｈＫｎｏｗｎ，ｇ［］Ｔｏｉ－ｔａｌＳｚｅＪ．Ｃｏｍｕｔｉ２００６７８４３６９３７８．ｐｎｇ：，，［］（）２９ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究３７ＴａｎＺ－？ＷｕＹ．ＯｔｉｍａｌｓｅｍｉｏｎｌｉｎｅａｌｇｏｒｉｔｈｍｓｆｏｒｍａｃｈｉｎｅｃｏｖｅｒｉｎｇＪ．ＴｈｅｏｒｅｔｉｃａｌＣｏｍ，ｐ［］［］ｔｅｒＳｃｉｅ２００７３７２１６９－８０ｕ．ｐｎｃｅ：，，（）３８ｉＹＨｕＺ－ＪａｎｇＪＷｅｎｅｔａｌ．Ｐａｒａｌｌｅｌｍａｃｈｉｎｅｃｏｖｅｒｉｎｗｉｔｈｌｉｍｉｔｅｄｎｕｍｂｅｒｏｆｒｅｅｍ，，ｇ，ｇｐｐ［］ｉ＿ｔｏｎｓＪ■Ｂ辑２〇ｌ４２９１８２８．高校应用数学学报英文版：，，［］（）⑴３９ＬｉＫＺｈａｎＨＪＣｈｅｎＢＹｅｔａｌ．Ｕｎｉｆｏｒｍａｒａｌｌｅｌｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｓｗｉｔｈ，ｇ，ｇ，ｐｇｐ［］ｉ－ｆｉｘｅｄｍａｃｈＪ．ＯｔｉｉｚａｔｉｏｎＬｅｔｔｅｒｓ２０１６１１４．ｎｅｃｏｓｔｐｍ：，［］４０ＨｏｒｏｗｉｔｚＥｌｌｉｓＳａｈｎｉｅｔａｌ．ＣｏｍｕｔｉｎｇＰａｒｔｉｔｉｏｎｓｗｉｔｈＡｌｉｃａｔｉｏｎｓｔｏｔｈｅＫｎａｓａｃｋ，，，ｐｐｐｐ［］－Ｐｒｏｂｌｅｍ．ｒｎａｌｏｆｔｈｅＡｃｍ１９２１２．ＪＪｏｕ７２：２７７２９２，，［］（）４１ＬｉＫＺｈａｎＸＬＹＴ？ｅｕｎｅｔａｌ．Ｐａｒａｌｌｅｌｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｒｏｂｌｅｍｓｉｎｒｅｅｎｍａｎ，ｇ，ｇ，ｇｐｇ［］ｕｆａｃｔｕｒｉｎｉｎｄｕｓｔｒ－ｇｙＪ．ＪｏｕｒｎａｌｏｆＭａｎｕｆａｃｔｕｒｉｎｇＳｙｓｔｅｍｓ２０１６３８：９８１０６．，，［］３０ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究附录攻读学位期间的研宄成果发表论文：刘淑丹．云制造环境下资源受限的同类机调度问题．蒋义伟，周天和Ｊ浙江理工大学，［］学报．（录用）３１ 浙江理工大学硕士学位论文云制造中资源调度问题的算法研究致谢时光飞逝，我的研宄生学习生活就要结束了，我在浙理工度过了人生中最美好的两年半的研宄生时光。带着满满的收获，马上就要离开校园踏入社会，心中有太多的不舍和眷恋。回想在母校读书的时光，对那些引导我、帮助我、激励我的人，我的心中充满了感激。首先要感谢我的导师蒋义伟教授，他渊博的专业知识，严谨的治学态度，精益求精的工作作风，诲人不倦的高尚师德，朴实无华、平易近人的人格魅力对我影响深远。不仅使一各方面的素质得到了提高。本论文我的知识结构和科研能力上了个新台阶，更重要的是从选题到完成一，每步都是在导师的指导下完成的，倾注了导师大量的心血，在此我向我的导师蒋义伟教授表示诚挚的谢意和崇高的敬意！我还要感谢组合优化课题组的胡觉亮教授、韩曙光副教授和董建明副教授，他们在课堂上给我讲授学科专业知识，为我研宄生的学习生涯和毕业论文的写作上打下了基础，在生活中都给予了我很大的关心和帮助，他们的敬业精神和为人为师为事的作风让我受益终一身！。在此我要向他们深深地鞠躬感谢９１５实验室的师兄、师姐、师弟、师妹，他们陪我度过了有意义的研宄生生活，一！让我在学术这条路上有人起并肩作战，讨论研宄问题。感谢他们对我的帮助感谢我的室友刘燕、李冰荣、卢琳珍。她们让我的研宄生生活充满了温暖与快乐。愿友谊长存！一特别感谢我的家人在我求学生涯过程中给予我无私的关怀与照顾，如既往地支持一我点成就都离不开他们的支持！、鼓励我，我所取得的每一最后！，再次感谢所有关心、帮助和支持过我的人们３２