11-作业排序.pptVIP

第11章 作业排序 第11章 作业排序 例： 某文印社专门为律师事务所提供复制法律文件的服务。在这周的开始，有5位顾客提交了他们的订单，原始数据如下表。 所有的订单都要使用唯一的一台彩色复印机。文印社经理需要决定5个订单的加工顺序。 应安排怎样的顺序？ 例题 方案1：先来先服务 例题 方案2：加工时间最短的订单优先加工 例题 方案3：最早交货期最早加工 例题 方案4：后到先服务； 方案5：随机加工； …… 排序的基本概念 (Sequencing) 排序——给出零部件在一台或一组设备上加工的先后顺序的工作。 注意区别： 作业计划是安排零部件（作业、活动）的出产数量、设备及人工使用、投入时间及出产时间。 作业排序和控制的功能 分配订单、设备和人员到各工作中心或其它规定的地方； 决定订单顺序； 对已排序作业安排生产； 车间作业控制。包括： 在作业进行过程中，检查其状态和控制作业的速度； 加快为期已晚的和关键的作业。 车间作业控制的主要工具 甘特图(Gantt Chart) 输入/输出控制(Input/Output Control) 派工单(Dispatching) 计算机辅助作业控制 作业排序的目标函数 作业排序的约束条件 具有的生产资源 必须完成的生产任务 操作工艺限制 作业排序的优先规则 最短的工序优先加工； 先到先服务； 后到先服务； 最早交货期最早加工； 最早开始的作业最早进行； 加工时间最长的先加工； 优先加工后续工序最多的工件； 优先选择临界比最小的工件： 随机次序； …… 排序问题的分类 根据机器数的多少 单台机器的排序问题 多台机器的排序问题 根据加工路线的特征 单件车间排序(Job Shop) 流水型排序(Flow Shop) 根据工件到达系统的情况 静态排序 动态排序 根据参数的性质 确定型排序 随机型排序 根据要实现的目标 单目标排序 多目标排序 排序问题的表示 常用下列符号表示不同的排列问题： n/m/A/B 式中：n：工件数； m：机器数； A处填写：F：流水车间排序； P：流水车间排列排序； G：单件车间排序； B：目标函数，通常是使最长流程时间Fmax最短。 最长流程时间Fmax的计算 例11.1 有一个6/4/P/Fmax问题，其加工时间如下表所示。当按顺序（6，1，5，2，4，3）加工时，求Fmax。 Fmax的计算 解：按顺序（6，1，5，2，4，3）列出加工时间矩阵： 排序常用的符号 Ji----工件i，i=1,2,....n di----工件i的交货期 Pi----工件i的加工时间, , pij----工件i在机器j上的加工时间, j=1,…,m 单台机器的排序问题 单台机器排序的目标函数 1) 平均流程时间最短 例题：求平均流程时间最短的排序问题 采用SPT原则：按工件加工时间的长短，按不减的顺序从小到大安排各项作业。 例：一个车间有一台加工中心，现有5个工件需要该机器加工。相关的加工时间和要求完成时间（交货期）如下表所示，求平均流程时间最短的作业顺序。 解： 解：根据SPT原则，得出：J4 -J5 -J1 -J2 -J3 有关项目的计算： 例题：求最大延期量最小的排序问题 采用最早交货期（EDD）原则：交货期最早的最早加工。 例：借用上面的例子，求最大延期量最小的作业顺序。 解： 两台机器的排序问题 两台机器排序问题的目标 两台机器排序的目标是使最大完成时间（总加工周期）Fmax最短。 两台机器排序问题的算法 n/2/F/Fmax问题举例 例：有五种零件，均须先在车床（A）上加工，再在铣床（B）上加工。车床和铣床各一台，各零件的加工时间如下表。 试对五种零件的加工进行排序。 Johnson算法应用 解：应用Johnson算法， 得出流程时间最短的加工顺序： J4？—J1—J2—J3—J5— J4？ 例题 例：某一班组有A、B两台设备，要完成5个工件的加工任务。每个工件在设备上的加工时间如下表所示。求总加工周期最短的作业顺序。 解： 表中最小加工时间值是1个时间单位，它又是出现在设备1上，根据约翰逊法的规则，应将对应的工件4排在第一位，即得： J4 - * - * - * - * 去掉J4，在剩余的工件中再找最小值，不难看出，最小值是2个时间单位，它是出现在设备2上的，所以应将对应的工件J1