第1章 调度概念、要素与架构
调度 (scheduling) 是实际生产系统的核心，与计划 (planning) 和执行等环节紧密相关。调度已被不同学科 (如机械、交通、计算机、管理等) 学者从不同角度进行了广泛研究，通过不同视角认识调度的本质，可充分利用不同研究观点各自的优势取长补短。由于调度是包含四类组件 (任务 (task)、资源、约束和目标) 的组合优化问题，可将其定义为一组任务到一组资源上的映射，满足约束条件下实现一个或一组目标的优化。调度问题非常广泛，可根据如下四类组件划分角度对其进行刻画。任务间的关系可分为三种类型：独立、线性约束和非线性约束。资源可分为四类：物理设备、人力、资金和信息。约束也可分为四类：任务约束、资源约束、任务-任务约束和任务-资源约束。优化目标可简单地划分为三类：单目标、多目标和超多目标。由于绝大部分调度问题是 NP 难的，基于人工智能、大数据和云计算，提出“算法 + 知识 + 数据 + 算力”的新型智能复杂调度框架。
1.1 引言
数十年来调度一直是制造、交通运输、计算机 (包括云计算、服务计算)、管理和自动化等多学科的热门话题，不同学科的调度问题具有不同特征。
调度*早受到制造业关注 [1]，即如何合理地为一组给定任务分配加工机器和必要工具，以*小化一个或多个目标 (如*大完成时间或 makespan、预算、成本等)，或*大化一个或多个目标 (如资源利用率、能源消耗等)。实际制造系统中存在许多调度优化问题 (如组件生产调度、零部件生产调度、工人工班安排、组装任务调度)。生产企业处于不同岗位的角色关注不同目标，如企业领导关注如何*小化工期、*小化零配件生产成本、*小化能源消耗、*大化资源利用率，而生产工人则期望收入*大化。调度通常受到各种用户需求或条件约束，如产品需按时交付、工人技能水平参差不齐、预算受限等，实际应用中各种复杂约束使得调度问题异常复杂。如何为这类问题找到*优解甚至可行解非常难，因此，通常需要对一些约束进行简化甚至完全不考虑，常见的经典生产调度包括单机器调度、作业车间 (job shop) 调度、流水车间调度、开放车间调度和项目调度等。因此，实际工程应用调度和调度理论研究间存在一定差距。技术变革推动着制造业等行业快速发展，调度问题越来越接近实际，待研究的调度问题也越来越复杂。除核心制造企业外，包括各级供应商、客户等在内的整个供应链全局优化等越来越受到重视，实际制造过程在横向和纵向上的调度优化问题及其相互关系如图 1.1所示。另外，智慧制造、网络化制造和云制造等造成资源地理分布、产品回收、可持续制造和客户需求反馈等各类新型复杂约束条件，使相应的调度问题变得更加复杂。过去几十年中，有大量关于制造调度的研究，仅综述文章就超过 70 篇，主要包括工业 4.0、流水车间 (flow shop)、作业车间(job shop)、钢铁生产、网络化制造、可持续制造、工艺规划和调度集成与单机系统等。
图 1.1 制造系统中的调度问题
交通运输行业有许多调度问题，即在不同约束下如何通过运输工具 (如船舶、飞机、卡车、火车、管道等) 运输物品，典型的约束条件包括有限空间、装载能力、等待时间、周转时间、能源消耗等，常见的运输方式有海运、陆运和空运。海运优化问题包括集装箱调度、邮轮航线规划、船舶路线选择、货物路线选择、船队调度/分配和海上石油运输等；空运优化问题包括直升机路线规划、空勤人员安排等。陆运优化是交通运输调度中研究*多的问题，包括车辆路线规划、旅行计划、车辆出发时间优化、公交车调度、列车编组、机车路径规划和列车调度等。这些调度问题中大多数都是经典 TSP(旅行商问题) 的变体。
手术室是大部分医院的关键资源，如何为多位不同紧急程度的患者同时合理安排多类资源 (如手术台、特种医疗设备、床位、手术医生、护士、麻醉师等) 是很难的问题。典型优化目标通常考虑*大化外科手术资源、*小化医疗费用、*小化等待时间、*小化完成时间或完工时间等，或者同时考虑多个目标。考虑这些目标的角色也不同，医院管理者希望*大限度地利用有限医疗设备和人力资源，而患者希望*大化自己的满意度并*小化费用。目前对外科规划、手术台调度、主刀医生调度等主流调度问题都有不同程度的研究。实际手术室调度问题的许多不确定因素 (特别是许多人为操作通常都是不确定的)，已有研究基本都不加考虑或者假定为确定的；外科技术的发展推动着更多调度问题的出现，如基于互联网的远程专家、远程医疗设备综合外科手术调度等。过去几十年中已有大量外科手术调度文献，部分研究将相应问题归结为车间作业调度、机器调度、工作流和智能外科手术调度等。
自动化行业的调度问题更侧重于实际应用，如自动化制造系统 (AMS)、自动导引车 (AGV) 调度、建筑自动化调度、智能家居电力调度等。AMS 中企业领导关注各种约束 (如预算和截止日期) 条件下的制造过程如何合理调度以减少能源消耗或提高资源利用率；在弹性制造系统或自动化仓储中，AGV 广泛用于不同地点间的物料运送，AGV 调度很重要，路径容量、网络布局和任务优先级等约束提高了该类问题的难度；建筑行业的一个重要问题是如何满足时间和成本要求的项目施工，其中任务间具有复杂的偏序约束关系；智能家居系统中对家电进行合理调度可以在满足硬约束和 (或) 软约束下降低功耗。与其他领域类似，实际应用的自动化调度问题与相应的调度研究间也存在一定差距。自动化技术的发展也将带来越来越多、更为复杂的调度问题。
管理科学中有许多与其他领域类似的调度问题，如能源管理、运营管理、供应链、物流、医疗保健管理、库存管理、项目管理和生产管理，其中项目调度是项目管理的关键，也是管理科学*受关注的问题之一。项目调度中的任务是包含在项目中的活动 (activity)，通常不同活动对不同类型资源 (如资金、人员、设备) 的需求不同，不同用户关心的优化目标也不同，常见的目标有*小化项目工期、*小化项目成本、*大化项目收益、满足截止日期的性能优化等。项目调度问题在实际应用中广泛存在，已有研究可从不同角度进行分类，如单项目/多项目调度、单模式/多模式/无限模式项目调度。在过去几十年中，研究*多的是资源受限项目调度问题 (RCPSP)，并由此产生很多变体问题，如资源受限抢占式项目调度问题 (PRCPSP)、资源受限多模式项目调度问题 (MRCPSP)、资源受限多项目调度问题 (RCMPSP)、多目标资源受限项目调度问题 (MORCPSP) 和不确定资源受限项目调度问题等。
计算机系统中存在大量的调度问题，*基本的就是操作系统中的进程 (process)或线程 (thread) 调度，即如何合理地将用户程序创建的进程或线程调度到计算机系统中的 CPU 等资源上以优化某个或某些指标 (如 CPU 利用率、吞吐量、等待时间、响应时间等)，由于进程或线程通常彼此相互独立，采用的主要调度规则有先来先服务 (FCFS)、*短作业优先 (SJF)、轮询调度 (RR) 和优先权调度 (PS) 等。但这些简单规则并不一定适用于地理分布计算资源 (如服务器)间有通信开销的分布式计算场景，通信开销会推迟任务的完成时间，甚至使其超过截止期；分布计算资源可能同构，也可能异构 (一般指具有不同处理速度)，故考虑计算和通信开销的调度将不再简单。由于有限的本地计算资源难以满足云计算中任务的巨大资源需求，假定具有无限云资源的云计算就成为任务分配理想模型，云计算架构主要包括三个层次：基础设施即服务（infrastructure as a service，IaaS)、平台即服务 (platform as a service，PaaS) 和软件即服务 (software as a service，SaaS)，不同资源租用方式 (预留、按需和竞价计价) 等新属性和约束为该类系统带来许多调度难题。后来出现的边缘计算技术在一定程度上可降低任务的通信开销，但边缘计算资源的计算能力远不如云计算资源，如何在通信开销和边缘计算能力之间进行平衡又产生另一大类调度问题；云计算和边缘计算调度的资源基本单位是虚拟机 (virtual machine，VM) 而非 CPU。单机系统中的程序由操作系统创建的进程或线程执行，随着实际程序功能的迅速扩大，一台计算机往往难以单独执行，面对这样的需求，面向服务架构 (SOA) 框架提供了一种解决方案，SOA 是一种组件与服务紧耦合的一体化 (monolithic) 框架，服务及服务间的切换需要大量资源，导致巨大资源浪费；后来出现的微服务为松耦合框架，每个微服务都仅需要一个容器，一个 VM 里可配置多个容器；与 SOA 应用 (application) 相比，微服务具有更多偏序约束关系。尽管两类应用都可刻画为工作流调度，但微服务调度比 SOA 应用调度困难得多；如何将容器配置到 VM和服务器也存在许多优化问题。大数据中采用 MapReduce、Spark 等模型在云计算环境下进行数据块处理时，如何合理地将这些任务 (Map 任务、Reduce 任务、Spark 作业、Spark 级段或 Spark 任务) 调度到云资源，对大数据计算性能至关重要。在过去几十年中，有大量关于计算机系统中的调度问题的研究，关注对象包括软件定义系统、大数据、云计算 [2]、网格计算和多处理器系统等的任务调度。
此外，调度还存在于其他一些学科和实际应用中，相应的示意图如图 1.2所示。
图 1.2 不同学科和应用中的调度问题
1.2 什么是调度
定义 1.1 调度是一个映射过程，即如何将一组任务或活动在满足一组约束的条件下映射到一组资源上，以*优化 (*大化或*小化) 给定目标 (或目标向量)。调度确定出任务的执行顺序及它在资源上的开始和结束时间，包含任务、资源、约束和目标四要素，如图 1.3 所示。
图 1.3 调度的组件
任务：所有要处理的事项、要执行的动作或要执行的程序都可视为任务，任务的所有属性 (如处理时间、优先级等) 在调度前定义 (定义于计划阶段，下面将详细叙述)，任务也可视为被服务对象或服务消费者。极端情况下上述学科应用涉及的调度算法，其执行过程本质上也可视为计算任务，即操作系统为这些调度算法的实现程序创建进程或线程，并将进程或线程调度到处理器上执行。为简化起见，下面涉及的被安排事项 (作业、任务、活动、操作、进程、线程、零件、物品、容器等) 通称为任务。
资源：服务提供者提供的服务，通常调度所考虑的资源是有限的 (如果资源足够丰富，则不需要调度)，常见的资源有机床、CPU、服务器、虚拟机、内存、I/O 设备、登机口、公共汽车、乘务员、外科医生、护士、病床、节点、插槽、教室、工人等。
约束：通常调度问题的解空间很大，但由于各种约束条件的限制，并非所有解都可行，这些约束将整个解空间的可行解分割为多个孤岛 (实际上对于调度问题，这类离散优化解之间都不是连续的，这里仅将相对集中的一些解当成一个孤岛)，常见的约束条件有交货期 (due date)、截止时间、优先级、安全性、隐私、预算、可用性、可靠性、到达时间等。. 目标：调度的目的是通过构造或设计出算法，从所有孤岛中找到*优解 (调度或时间表)，常见的优化目标有完成时间、总执行时间、迟延、响应时间、吞吐量、等待时间、租赁成本、能源、利用率、资源均衡、服务质量 (QoS) 等，有时同时考虑多目标 (两个或三个目标) 或超多目标 (至少四个目标) 的优化。
调度的组合优化特性使得多项式时间复杂度内在孤立的多个可行解孤岛上找到*优解几乎不可能，搜索是目前解决这类离散优化问题的唯一方法。绝大多数调度问题都是 NP 难的，在用户可接受的有限计算时间内找到*优值几乎不可能，实际可接受的方案是找到近似*优或甚至可行解即可。此外，搜索算法的鲁棒性也很重要，即所设计算法不仅对某些特定问题有效，而且对所有该
展开
