本文是一篇工商管理论文，本文研究的是考虑机器固定使用成本的同类机调度问题，即资源使用方以固定的费用租用制造资源，从而获取一天或者一个周期内制造资源的使用权，而具体的使用时间由自己决定。
第一章 绪论
1.1 研究背景
制造业作为我国的支柱产业，自从改革开放以来，一直保持较好的发展态势，持续快速发展，进一步推动了工业化和现代化的进程，增强了我国的综合国力，有力地稳固了我国作为世界大国的地位。但是，与世界先进水平相比，我国制造业仍然大而不强，在很多方面都存在着明显的差距，如自主创新能力、资源利用效率、产业结构水平、信息化程度、质量效益等。进一步，随着我国人口红利的消失，人工费用的增长，依靠人力的传统制造业的发展道路已经越走越窄，于是，转型升级和跨越发展的任务既紧迫又艰巨。
从管理的角度来看，传统制造和云制造的差别可以总结如下：在传统制造管理理论中，假定所有的制造资源由制造商购买，制造商的目标是充分利用自己的资源，提高生产效率，获得更多的利润。所以没有必要考虑机器成本运营管理的经典理论。然而，在云制造环境下，制造资源来源于企业外部，其所有者与使用者不同。因此资源使用方会采用租用的方式来获取资源的使用权，从而云制造资源调度的一个典型特点就是需要考虑机器的使用成本，制造资源的用户应统筹安排处理能力和租用的机器成本。本文研究的是考虑机器固定使用成本的同类机调度问题，即资源使用方以固定的费用租用制造资源，从而获取一天或者一个周期内制造资源的使用权，而具体的使用时间由自己决定。
随着“互联网+”和工业 4.0 的推进，我国更加关注云制造的发展。本文在现代制造业的发展趋势下，在云制造的背景下，研究了考虑机器固定使用成本的同类机调度问题。
........................
1.2 研究意义
在理论研究方面，本文进一步拓展了同类机调度问题，机器的速度不同。另外，本文将机器的使用成本考虑到问题中，而不是单纯地研究作业调度的问题，综合考虑成本与生产时间这两个因素，这为以后的调度问题的研究带来了新思路，也提供了一定的理论基础。再者，云制造是一种新型生产制造模式，成为制造业研究领域的研究热点，目前的研究还比较少，本文在云制造背景下研究调度问题，这也为以后关于云制造的相关研究提供了一定的研究基础。
在实践方面，同类机调度问题是一类极具应用背景的新型调度优化问题，在现代制造业的生产制造过程中具有广泛应用。随着制造业的发展，制造资源不再单一化，不同的制造资源或者制造设备的加工速度也不同，本文研究的就是机器加工速度不同的调度问题，这更符合现实，更具现实意义。在现代制造业中，大量生产已经过时了，充分利用资源，将资源的价值发挥到最大，才是现在的目标。本文的调度目标就是在总成本的预算范围内，最小化 makespan，提高资源利用效率。这一点相当具有现实价值。另外，在现代制造业中，云制造必将逐步发展，本文也是站在现实的角度，在云制造背景下研究了调度问题。这符合制造业的现实和未来的发展趋势。
因此，本文研究的云制造背景下考虑机器使用成本的同类机调度问题，在理论研究与实践中都具有重要意义。
............................
第二章 相关概念及理论基础研究
2.1 相关概念研究
在制造管理的过程中，最常见的问题是如何充分有效利用企业内外部的制造资源，最终的目标是达到使得客户满意和企业获取最大利润这样一个双赢的局面。为此，企业需要在有限的资源和成本预算下，生产加工作业，按时按量地完成任务，满足客户的需求。从而生产调度问题受到了重大关注。事实上，生产调度问题可以这样描述：给定一个待加工的作业集和一个加工作业的机器集，将所有作业按照某种规则分配到机器上加工，直到所有作业完成加工。其中，每台机器可以加工不同的作业，而每个作业也可以由不同的机器加工，并且，一台机器在同一时间不能加工不同的作业，而一个作业在同一时间也不能由不同的机器加工。调度的目标是如何充分利用现有的制造资源如机器设备，在满足一些限定条件如总成本预算的限制或工期的限制等条件的基础上，合理的安排作业的加工顺序，完成加工任务并达到调度目标。
调度问题，亦称为排序问题，是组合最优化领域中一类重要的问题。简单来说，就是将一批杂乱无章的个体，按照一定的规则进行排列的过程。它主要的产生背景是机器制造，后来被广泛应用于其他领域，如计算机系统、运输调度、生产管理等。无论是运筹学界和计算机科学界，还是工程学界和管理学界，排序问题的影响都很大，小到学校课程表的制订，普通的生产部门的计划安排、人员调度，大到宇宙的复杂庞大的飞行计划，都要用到排序的理论和算法。在理论方面，它和算法设计与分析、计算复杂性理论密切相关。
...........................
2.2 相关理论基础研究
云计算是一种新型的信息技术，它既是一种通过网络提供服务的应用，又是通过数据中心的软件和硬件系统提供一种服务。Armbrust et al.把服务分为SaaS(Software as a Service)，IaaS(Infrastructure as a Service)，PaaS(Platform as aService)等。杨善林和罗贺分析了云计算的概念、特征、层次、分类等，梳理和总结了基于云计算的多源信息服务系统研究，从管理的角度对云计算的多源信息服务系统进行了综述，探究了云计算环境下的多源信息服务的一些关键技术。
在过去几年中，云制造受到了国内外研究者的关注，这个研究领域很广。云制造是云计算的思想应用在制造业所产生的一种新型制造模式。云制造理念是由我国著名的信息化专家李伯虎院士率先提出来的。在国家科技计划的支持下，产、学、研、用等近50个单位，以集团级和中小企业的云制造应用为背景，在关键技术、支撑平台及应用技术方面，已取得阶段性成果。在2001年，Rauschecker et al.描述了用于设想新一代的可配置的制造系统的云计算服务的模式。他们描述了关于云制造的动力和挑战，通过基于制造服务描述建立一种适当的制造服务环境阐述了新兴技术支持这种设想。Laili et al.提出了一种新的综合模型用于在云制造系统中优化配置计算资源，提出了一种新的免疫算法用于解决OACR问题。在2010年，李伯虎等为了解决更加复杂的制造问题，开展更大规模的协同制造，分析了当时一些现有的网络化制造模式（如：应用服务提供商、制造网格等）在应用推广等方面遇到的问题，阐述了云计算服务模式、云安全、高性能计算、物联网等理念和新技术对解决网络化制造中运营、安全等问题的契机。在此基础上，他给出了云制造的定义，分析了云制造模式与应用服务提供商、制造网格等网络化制造模式的区别，并提出了一种云制造的体系结构，讨论了实施云制造过程中所需攻克的关键技术和所取得的成果。进一步，李伯虎等简述了制造业信息化的发展趋势，详细讲述了云制造的研究进展，也提出了云制造的未来发展面临的挑战，他认为，未来所需攻克的重要技术，不仅包括云计算、物联网、语义 Web、高性能计算、嵌入式系统等技术的综合集成，还包括基于知识的制造资源云端化、制造云管理引擎、云制造应用协同、云制造可视化与用户界面等技术。杨海成认为云制造是一种制造服务，以先进的信息技术为媒介，为有需求的行业和企业等服务对象提供产品开发、生产销售等全生命周期的制造资源集成和共享等服务。Tao et al.从技术层面给云制造下了定义：云制造是一种面向服务的新制造模式，它整合网络化制造、云计算、物联网、虚拟化和面向服务计算等技术，共享和管理制造资源。Xu认为云制造是一种让资源需求方可以根据自己的需求从云服务平台处获取制造资源和能力，以最少的管理任务及云服务提供商间的最少交互来快速提供并释放资源的一种制造模式。
...........................
第三章 面向标准作业的考虑机器使用成本的同类机调度问题.............................. 12
3.1 问题描述 ............................... 12
3.2 不可中断问题 ............................. 13
第四章 面向普通作业的考虑机器使用成本的同类机调度问题.............................. 24
4.1 问题描述 ................................... 24
4.2 不可中断问题 ................................... 25
第五章 总结与展望..................... 36
5.1 论文工作总结 ............................ 36
5.2 展望 ............. 36
第三章 面向标准作业的考虑机器使用成本的同类机调度问题
3.1 问题描述
本节中，为了解决这个问题，我们首先必须在给定的总成本预算U 的范围内选择一些合适的机器。与第三章中选择机器相同，在选择机器过程中，有一些机器拥有更快的加工速度，但我们没有足够的预算去租用它们，所以必须跳过这些机器。所以，同样，我们用变量h来表示第一次跳过的机器的序号，并用S表示这第h个机器的速度，用集合A表示已选机器的机器集，用U表示已选机器集 A中所有机器的使用成本之和，用a表示已选机器集 A 中机器的数量。一旦已选机器集A确定了，那么 Qm|ptmn,U ,p|Cmax问题就可以退化为 Qa|ptmn,p|Cmax问题了。此时，由于本章研究的是标准作业的调度问题，即作业的加工时间相同，都为p，因此我们可以将
