前言:
现在兄弟们对“云计算任务调度算法”大约比较重视,看官们都需要学习一些“云计算任务调度算法”的相关内容。那么小编同时在网上收集了一些关于“云计算任务调度算法””的相关内容,希望朋友们能喜欢,各位老铁们一起来了解一下吧!引自:《智能调度》(作者:李新宇, 张利平, 牟健慧)
「 1. 调度的作用 」
调度是一个复杂的决策过程,它通过将一段时间内的特定资源分配给特定任务,以期实现一个或多个目标的优化。资源的形式多种多样。对于制造业而言,资源主要指的是生产资源,可表现为车间里的机器、加工所用模具、刀具等;对于服务业而言,资源可以表现为机场的跑道、建筑场所中的施工单位、地产开发过程中的土地资源、医院内的手术室等。任务的形式同样种类繁多,可以是工厂内的一个加工操作、飞机的起飞和到达、建筑工地内的一个项目、某位病患的一台手术等。优化目标包含多种形式,如最小化最后一个任务的完成时间、最小化成本、最小化任务拖期等。
随着信息时代的不断发展,调度在大多数的制造业、服务业及存在信息处理需求的行业扮演着愈发重要的角色。
以汽车流水生产线为例,世界第一条大规模汽车流水生产线由美国福特汽车公司于1913年推出,通过对装配过程进行合理分工,极大地提升了工厂生产效率。整个汽车生产流程由最初的传统“全能型员工”流程转变为采用传送带供应的流水线生产模式,使一台T型福特汽车的组装耗时缩短50%,开创了新的、高效的汽车制造流程,推动福特获得了重大的成功。时至今日,丰田汽车依靠以成本控制为核心、计划管控为手段、消除一切无效劳动和浪费为目标的精益生产模式,在全球汽车市场的利润率仅3%~6%时,丰田汽车2019年利润率仍然保持在9.2%。
调度对于流程工业的发展和进步同样具有重要意义。石油化工是典型的流程工业,其生产设备众多,如何在既定生产计划下,根据物料平衡和实时的物料性质制定生产资源调配时间序列和设备操作条件是企业稳定生产和实现效益最大化的必要条件。
经过数十年的发展,我国已成为世界上门类最齐全、规模最大的制造业大国,但普遍存在生产效率低、能耗物耗高、安全环保问题突出等现象。其核心原因之一是缺乏实现生产工艺优化和全流程整体运行优化的高效调度方法。此外,我国的“中国制造2025”同样强调了制造业在国民经济中的主体地位,将智能制造作为主攻方向。
1)制造业中的调度[1]
制造业是国民经济的主体,是立国之本、兴国之器、强国之基。制造业是指利用某种资源(含物料、能源、设备、设施、工具、资金、技术、信息和人力等),按照市场要求,通过制造过程,转化为可供人们使用和利用的工具、工业品与生活消费产品的行业。合理的调度方案能够有效提高制造业的生产效率,实现资源利用的最大化。我国为了制造业的转型升级曾花费数十亿美元引进和开发了制造资源计划(MRP Ⅱ)、企业资源规划(ERP)等软件,但绝大多数没有得到很好的使用,主要原因之一是“生产作业计划”这个技术瓶颈没有得到突破。车间内的生产计划和调度方案仍采用传统的经验和人工方法,导致工业软件的使用与企业加工现状出现断层(见图1)。因此,智能调度技术不但要在错综复杂的约束条件中找到可行方案,还需在难以计数的可行方案中找到满足优化目标的较优生产作业计划,从而提高企业的生产效益。
图1 制造业信息流图[1]
2)服务业中的调度[1]
服务业包括交通、信息、医疗、餐饮、银行等多个行业。作为第三产业,服务业具有覆盖面广、内容综合性高、分散性大等特点,更加需要智能调度技术对场地、资源、人员等进行统一协调与管理。服务业中的调度主要集中在各种服务行业中的排班、排队等问题,其目标是追求效率最高、顾客满意度最大化等。图2展现了服务业中的信息流。
图2 服务业信息流图[1]
新中国成立后,经过70多年的发展,我国工业成功实现了由小到大、由弱到强的历史大跨越,使我国由一个贫穷落后的农业国成长为世界第一工业制造大国。从21世纪初开始,我国正在逐步由制造大国向制造强国的方向转变。在调度及相关学科的支持下,制造业基本完成了现代化转型升级,正在向着数字化、网络化、智能化的目标不断前进。在未来,智能调度仍将在制造业和服务业等领域发挥着积极的作用,激发行业的创新驱动力,推动我国快速发展为制造强国。
「 2. 调度的发展趋势 」
市场需求和科技进步会催生新的生产方式,而新的生产方式又会影响制造系统的功能特征和生产组织模式。用户对产品的多样化、个性化需求,使得生产方式已由传统的大批量生产向大规模个性化定制生产发展。目前,工业4.0正给生产技术和生产组织模式带来变革和创新,一些先进计算机与通信技术(如物联网、云计算、大数据、边缘计算等)的突破使得制造业变得更加柔性、高效和智能[2]。精益生产、敏捷制造、可重构制造、云制造、智能制造等先进生产模式得到了飞速发展与推广[3]。有效的调度是生产环节中的一个关键问题,它可以减少相应任务的处理时间,提高资源利用率,从而实现企业利润的最大化[4]。随着市场需求和新技术驱动下生产模式的变化,与之相适配的调度模式也必然要发生相应的变化。未来调度技术将朝着自适应自组织调度、大数据驱动调度、协同调度(供应链协同调度、云边协同调度、人机协同调度)以及基于数字孪生的调度等方向发展[5]。
1)自适应自组织调度
随着信息与通信技术的进步,工业生产逐步由集中式控制向分散式控制转变[6-7]。分散式控制提高了生产系统的柔性和敏捷性,生产系统中的每个资源都具有感知、分析、推理、沟通和执行的能力。在自适应自组织调度中,把整个分散式控制生产系统看作一个多智能体系统,每个资源就是其中的一个智能体,它可以根据部分信息和局部目标做出决策。目前,为了获得一个全局目标较优的调度方案,常用基于拍卖机制的协商策略来平衡智能体之间的局部目标冲突[8]。
2)大数据驱动调度
物联网技术在现代工业的应用增加了工业数据的数量和更新速度,生产过程中搜集到的实时数据包含大量有用信息,可以为后期调度方案的制定提供有益帮助[9]。这使得数据挖掘在智能制造中所起的作用越来越重要,大数据分析逐渐成为优化生产系统管理的关键技术和主要方法[10]。2020年,中国工程院发布的《全球工程前沿》将“基于大数据的智能制造系统生产调度技术”遴选为机械与运载工程领域的Top 10 工程开发前沿之一。在大数据驱动调度中,往往先基于历史数据,不断产生新的离线挖掘调度算法,再用这些算法更新算法库,最后根据生产系统的实时数据为用户推荐最佳调度方法[11]。
3)协同调度
供应链协同调度。在产品同质化问题突出的时代,市场竞争日趋激烈,用户对产品的多样化、个性化需求也不断增加。然而由于设备、原材料和劳动力成本激增以及供应链各环节信息的不对称,传统供应链管理面临着高成本、长周期、低质量和高风险的挑战。物联网、区块链等技术的发展加速了供应链各环节(涵盖供应、生产、销售等环节)的信息数字化、共享化进程,为供应链协同调度技术的实现提供了技术支撑和保证[12]。供应链协同调度在供应链精益化、绿色化、全球化、智能化过程中起着至关重要的作用[13]。
云边协同调度。物联网技术的进步给分布式制造企业带来了全新的挑战,如更低的延迟要求、不间断的服务需求和可靠的安全保障等[14]。当前的难点在于决策中心位于云端,调度系统和制造资源之间的远程连接会带来延时和不安全因素;虽然以边缘计算为代表的新兴技术手段在一定程度上提高了工厂(边缘端)的调度水平,但受限于边缘端的资源规模和计算能力,调度结果的质量不高[15]。为了提高个性化市场需求背景下生产系统的响应速度和全局优化能力,云边协同调度的研究十分必要。
人机协同调度。智能制造系统是一个集人、信息和物理为一体的生产系统,它的不确定性和复杂程度都非常高,传统的调度方法难以实现即时响应[16]。新一代人工智能技术的发展,使人机之间的智能协作成为现实,机器可以根据自身的感知、分析为生产系统的调度运营提供建议[17]。未来人与智能机器在物理、信息、决策等多个方面的互动会越来越频繁,人机协同调度的应用前景非常广阔。
4)基于数字孪生的调度
在现实生产场景中,一些动态事件和扰动时常发生,现有动态调度方法的响应速度和稳定性已无法满足智能车间的鲁棒性需求[18]。基于数字孪生的调度技术在新一代信息技术和制造技术驱动下,通过物理车间与虚拟车间的双向映射与实时交互,形成真实与虚拟共生的协同优化网络。物理车间主动感知当前生产状况;虚拟车间通过自组织、自学习、自模拟等方式进行生产状态分析、调度方案调整和决策评估。通过这种方式,可以立即锁定异常范围,并在短时间内提供出合理高效的应对措施[19]。基于数字孪生的调度将很快成为调度领域的一个新的研究热点。
参考文献
[1] PINEDO M. 调度: 原理算法和系统[M]. 张智海, 译. 北京: 清华大学出版社, 2007.
[2] ROSSIT D A, TOHME F, FRUTOS M. Industry 4.0: Smart Scheduling[J]. International Journal of Production Research, 2019, 57(12): 3802-3813.
[3] ESMAELIAN B, BEHDAD S, WANG B. The Evolution and Future of Manufacturing: A Review[J]. Journal of Manufacturing Systems, 2016, 39: 79-100.
[4] 潘全科, 高亮, 李新宇. 流水车间调度及其优化算法[M]. 武汉: 华中科技大学出版社, 2013.
[5] JIANG Z Q, YUAN S, MA J, et al. The Evolution of Production Scheduling from Industry 3.0 through Industry 4.0[J]. International Journal of Production Research, 2021, 43: 1-21.
[6] DOLGUI A, IVANOV D, SETHI S P, et al. Scheduling in Production, Supply Chain and Industry 4.0 Systems by Optimal Control: Fundamentals, State-of-the-Art and Applications[J]. International Journal of Production Research, 2019, 57: 411-432.
[7] MLADINEO M, CELAR S, CELENT L, et al. Selecting Manufacturing Partners in Push and Pull-Type Smart Collaborative Networks[J]. Advanced Engineering Informatics, 2018, 38: 291-305.
[8] LANG F, FINK A, BRANDT T. Design of Automated Negotiation Mechanisms for Decentralized Heterogeneous Machine Scheduling[J]. European Journal of Operational Research, 2016, 248(1): 192-203.
[9] ROSSIT D A, TOHME F, FRUTOS M. A Data-Driven Scheduling Approach to Smart Manufacturing[J]. Journal of Industrial Information Integration, 2019, 15: 69-79.
[10] DIAS L S, LERAPETRITOU M G. Data-Driven Feasibility Analysis for the Integration of Planning and Scheduling Problems[J]. Optimization and Engineering, 2019, 20(4): 1029-1066.
[10] KONG W, QIAO F, WU Q. Real-Manufacturing-Oriented Big Data Analysis and Data Value Evaluation with Domain Knowledge[J]. Computational Statistics, 2020, 35(2): 515-538.
[12] DOLGUI A, IVANOV D, POTRYASAEV S, et al. Blockchain-Oriented Dynamic Modelling of Smart Contract Design and Execution in the Supply Chain[J]. International Journal of Production Research, 2020, 58(7): 2184-2199.
[13] IVANOV D, DOLGUI A. A Digital Supply Chain Twin for Managing the Disruption Risks and Resilience in the Era of Industry 4.0[J]. Production Planning & Control, 2020, 24: 1-14.
[14] CHIANG M, ZHANG T. Fog and IoT: An Overview of Research Opportunities[J]. IEEE Internet of Things Journal, 2016, 3(6): 854-864.
[15] JIANG Z, JIN Y, E M C, et al. Distributed Dynamic Scheduling for Cyber-Physical Production Systems based on a Multi-Agent System[J]. IEEE Access, 2017, 6: 1855-1869.
[16] ZHOU J, YAO X, LIN Y, et al. An Adaptive Multi-Population Differential Artificial Bee Colony Algorithm for Many-Objective Service Composition in Cloud Manufacturing[J]. Information Sciences, 2018, 456: 50-82.
[17] RAESSA M, CHEN J C Y, WAN W, et al. Human-in-the-Loop Robotic Manipulation Planning for Collaborative Assembly[J]. IEEE Transactions on Automation Science and Engineering, 2020, 17(4): 1800-1813.
[18] TAO F, ZHANG H, LIU A, et al. Digital Twin in Industry: State-of-the-Art[J]. IEEE Transactions on Industrial Informatics, 2018, 15(4): 2405-2015.
[19] AGOSTINO I R S, BRODA E, FRAZZON E M, et al. Using a Digital Twin for Production Planning and Control in Industry 4.0[C]. In: Scheduling in Industry 4.0 and Cloud Manufacturing. Cham: Springer, 2020: 39-60.
标签: #云计算任务调度算法