摘要
排序问题是一类重要的组合最优化问题。排序问题普遍应用于管理等学科领域，是组合最优化的一类重要问题。调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。但是由于资源约束和工艺约束的并存，迄今计算复杂性理论表明，多数调度问题属于NP一hard(Nondeterministiepolynomial一Hard，非确定性多项式)难问题，目标解的搜索涉及解空间的组合爆炸。排序算法的竞争比分析是排序问题对算法风险的一种评估和保障，具有重要的理论意义和实用价值。
本文讨论了带有交货期和工件的加工时间可控的单机排序问题本文首先根据最优排序的性质确定了最优资源的分配方法并将问题转化为指派问题通过构造多项式时间算法确定最优排序#然后本文将学习效应与加工时间可控问题结合分别讨论了加工时间是线性资源函数和凸资源函数两种情况证明了该类问题是多项式时间可解的最后讨论了一种特殊情况学习因子是常数加工时间是凸资源函数给出了复杂性为O(nlogn)的算法通过运行此算法确定最优资源分配量和工件的最优排序。
关键词：排序单台机器,交货期,指派加工时间可控,资源分配.
摘 要………………………………………………………………………………………………4
ABSTRACT……………………………………………………………………………………….5
第一章 绪论……………………………………………………………………………8
1.1 课题研究的背景和意义8
1.2课题研究的目的意义和主要内容.9
1.2.1 排序问题的简述………………………………………………………………9
1.2.2 排序问题的求解……………………………………………………………10
1.2.3 算法复杂性的简介…………………………………………………………10
1.3 本章小结.11
第二章 带有交货期和加工时间可控的单机排序问题12
2.1 单机排序.12
2.1.1 符号说明 ………………………………………………………12
2.1.2 常用排序方法…………………………………………………13
2.2带有交货期和加工时间可控的单机排序问题14
2.2.1问题描述.14
2.2.2资源约束.16
2.2.3模型推广.19
2.3应用举例及计算结果23
2.4本章小结25
第三章 仿真与分析25
3.1车间调度仿真25
3.1.1 车间调度问题的描述25
3.1.2 车间调度问题的特点25
3.2仿真调度的原理和特点.26
3.2.1 仿真调度的原理26
3.2.2 仿真调度的特点26
3.3 仿真的基本方法………………………………………………………….27
3.3.1 仿真的三种方法27
3.3.2 仿真在调度中的作用27
3.3.3 车间生产仿真调度业务流程28
3.4 实例仿真……………………………………………………………………….29
3.6 本章小结.41
第四章 总结与展望42
参 考 文 献44
毕业设计小结45
致 谢 46
