第四章排序论讲述.pptx

第4章 排序问题 4.1绪论 4.1.1引例 排序问题产生的背景主要是机器制造，后来被广泛应用于计算机系统、运输调度、生产管理等领域。从普通的生产部门的计划安排、人员调度，学校课程表的制定，到宇宙飞船的飞行计划都要用到排序的理论和方法。 例4.1.1机械加工 一个机械加工车间要加工一批机器零件，每一个零件都有相同的工序，即按相同的顺序在几个不同的机床上加工，但每个零件在每个机床上的加工时间可能不同。如何安排加工顺序才能以最短的时间完成所有的零件。这是一个流水线排序问题。 例4.1.2 进程调度 在计算机多道程序操作系统中，并发执行多个进程，在宏观上同时执行多个进程，在微观上在任何时刻CPU只能执行一个进程。进程的到达时间是不同的，怎样调度这些进程才能使CPU的利用率最高或者进程的平均周转时间最短？这也是一个排序问题。 例4.1.3 机场的调度 机场的调度人员需要制定一个可行的方案，把登机门分配给降落的飞机，使机场的利用率最高或晚点起飞的飞机最少，这也是一个排序问题。 4.1.2排序问题的定义 排序问题是一类重要的组合最优化问题，它是利用一些处理机、机器或资源，最优的完成一批给定的任务或作业。在执行任务的过程中需要满足某些限制条件，如任务的到达时间、加工顺序等。最优指的是使目标函数达到最小，目标函数通常是对加工时间长短、处理机效率的描述。 处理机 只有一个处理机的排序问题为单机排序问题， 否则为多机排序问题。处理机的各种类型和环境描 述如下： 单处理机 同类机（平行机） 同速机 恒速机 变速机 多类机（车间作业） 同顺序作业 异顺序作业 自由顺序作业 柔性流水作业 任务和作业 排序中的约束条件主要指的是任务或作业的性质及在加工过程中要求和限制。 （1）加工时间向量 其中 表示任务 在处理机 上所需要的时间。 （2）到达时间 到达时间或准备时间 是任务 已经准备好被加工的时间。 （3）工期和截止期限 工期 是对任务 限定的完工时间。 （4）优先因子 优先因子 是一个权，表示任务相对于其他任务的重要程度。 任务被加工的一个重要约束是可中断或不可中断。若排序中每一个任务在加工时都可暂停加工，加工该任务的处理机可加工其他任务，以后也可在任意时刻任意处理机重新加工，这叫做可中断排序，否则为不可中断排序。 目标函数 目标函数主要有以下几种： （1）时间表长： 最后一个被加工完任务的完工时间，越小处理机利用率越高。 （2）平均加工流时间和加权总完工时间 平均加工流时间： 加权总完工时间： （3）最大延误 （4）加权总误工（total weighted tardiness） （5）加权误工任务数 4.1.3排序问题的分类 确定性排序和随机排序。 确定性排序：所有数据在进行决策之前都是已 知的。随机排序：在决策之前有些数据是随机的， 但他们的分布是已知的。 这两类排序我们假设： （1）任务或作业和处理机是有限的。 （2）在任一时刻任何处理机只能加工一个工件。 （3）极小化单一目标函数。 处理机、任务、目标函数三要素构成了排序问题。 因此，可以用三元 组 来表示排序问题。 域表示处理机的数量、环境和类型，它可以为： 1：单处理机 ：m个同速机 ：m个恒速机 ：m个变速机 ：m个处理机，流水作业 域表示任务或作业的性质、加工要求、限制，资源的种类、数量和对加工的影响等约束条件。 域表示要优化的目标函数。 例4.1.4 表示一个单机 、可中断的排序问题，任务有不同的到达时间 ，极小化的目标函数是加权总完工时间。 例4.1.5 表示一个任务集无关、不可中断、极小化的排序表长的同速机排序问题。 4.1.4排序问题的求解 可行排序与最优排序 绝大多数排序问题是从有限个可行解中找出一个最优解，使目标函数达到最小，在排序中可行解称为可行排序，最优解称为最优排序。 例4.1.8 给定排序问题 ，其中n