学位论文 > 优秀研究生学位论文题录展示

机器带中断的若干延误问题研究

作　者: 叶春花
导　师: 沈灏
学　校: 杭州电子科技大学
专　业: 运筹学与控制论
关键词: 平行机排序中断时间复杂性最坏情况界
分类号: O223
类　型: 硕士论文
年　份: 2009年
下　载: 8次
引　用: 0次
阅　读: 论文下载

内容摘要

本文研究机器带中断的排序问题。该问题可以描述为:两台平行机加工一批工件,加工过程中,由于某种原因,其中一台机器发生故障可能在某一个时刻产生中断,这使得安排在该机器上加工的工件无法及时加工,因而这些工件要么等待中断结束后继续在原机器上加工,要么转移到另一台正常运行的机器上加工,当发生故障的机器恢复加工后,安排在正常运行的机器上加工的工件也可以转移到恢复以后的机器上加工。（1）文章研究如何安排新的加工顺序,使得目标函数为误工工件个数（?）最小化;（2）两台平行机加工n个工件,文章研究如何重新安排工件的加工顺序,并将任意n个交工期限怎样分配给各个工件,使得目标函数（?）,（?）为最小,其中d_[i]是分配给工件J_i的交工期限。全文共分为四章。第一章是绪论,主要介绍组合优化、计算复杂性的基本理论,并对排序问题的背景、研究方法等知识进行阐述。第二章讨论问题（1）。当工件转移时间T=0时,证明问题（?）是多项式时间可解问题,本文给出了相应的算法,并证明了算法的最优性;当转移时间T>0时,问题（?）是NP难问题,对该问题文章提出了一个差界为1的多项式时间的近似算法,并给出了证明,算法的计算复杂度为O（nlogn ）。第三章讨论问题（2）。研究交工期限可分配的机器带中断的两台平行机排序问题,并将其推广到m台机的情形,当交工期限为（?）分配给先后加工的工件时,,考虑目标函（?）,文章给出了一个最优排序。对于上述给定的排序,当交工期限d₍[1], d_[2],……d_[n]按EDD序分配给先后加工的工件时,对上述目标函数文章证明是最优的。第四章是对全文的总结概括,并对以后的工作做了展望。

全文目录

摘要  5-6
ABSTRACT  6-9
第1章绪论  9-17
  1.1 组合优化问题  9
  1.2 排序问题相关知识  9-13
    1.2.1 排序背景与发展现状  10-11
    1.2.2 排序问题的表示  11-13
  1.3 算法和算法的界  13-15
    1.3.1 多项式时间算法与P 问题  13-14
    1.3.2 NP,NPC 和NP-HARD 概念  14
    1.3.3 近似算法和启发式算法  14-15
  1.4 论文概述  15-17
    1.4.1 机器带中断问题背景  15-16
    1.4.2 论文主要结果  16-17
第2章机器带中断的最小化误工工件数问题  17-25
  2.1 引言  17-19
  2.2 问题描述  19
  2.3 算法及定理  19-25
    2.3.1 问题（1）(?)算法  20-21
    2.3.2 问题（2）(?)算法  21-23
    2.3.3 问题（2）(?)的算法性能分析  23-24
    2.3.4 算法的计算复杂性  24-25
第3章交工期限可分配的机器带中断的排序问题  25-39
  3.1 引言  25-26
  3.2 问题描述  26-27
  3.3 算法设计  27-28
  3.4 预备知识  28-30
  3.5 主要定理及证明  30-39
第4章总结与展望  39-41
  4.1 主要结论  39-40
  4.2 工作展望  40-41
致谢  41-42
参考文献  42-45
附录  45

机器带中断的若干延误问题研究

内容摘要

全文目录

相似论文