带有交货期和加工时间可控的单机排序问题(论文)(任务书,毕业论文16000字,答辩PPT)
摘要
排序问题是一类重要的组合最优化问题。排序问题普遍应用于管理等学科领域，是组合最优化的一类重要问题。调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。但是由于资源约束和工艺约束的并存，迄今计算复杂性理论表明，多数调度问题属于NP一hard(Nondeterministiepolynomial一Hard，非确定性多项式)难问题，目标解的搜索涉及解空间的组合爆炸。排序算法的竞争比分析是排序问题对算法风险的一种评估和保障，具有重要的理论意义和实用价值。
本文讨论了带有交货期和工件的加工时间可控的单机排序问题本文首先根据最优排序的性质确定了最优资源的分配方法并将问题转化为指派问题通过构造多项式时间算法确定最优排序#然后本文将学习效应与加工时间可控问题结合分别讨论了加工时间是线性资源函数和凸资源函数两种情况证明了该类问题是多项式时间可解的最后讨论了一种特殊情况学习因子是常数加工时间是凸资源函数给出了复杂性为O(nlogn)的算法通过运行此算法确定最优资源分配量和工件的最优排序。
关键词：排序单台机器,交货期,指派加工时间可控,资源分配.
ABSTARCT
Scheduling problem is an improtan combinatorial opti-zation problem.Scheduling problem is widely applied impr-otant problems in combinatorial optimization.The schedul-ing of tasks according to production objectives and constr-aints,to detemine the specific processing route,time,mac-hine and operation eachobject processing.
Good scheduling strategy has a great role in improve economic benefits.But due to the coexistence of resource constraints and technological constaints,so the computati-onal complexity theory shows that,most scheduling problr-m belongs to NP a hard(Nondeter ministiepolynomial Har-d,non deteministicpolynomial) problem target search rela-tes to the combinatorial explosion of the solution space.S-orting algorithm of the comprtitive ratio analysis is the so-ft of algorithm the risks of a assessment and security,has the important theory significance and practical value.
This paper discusses the single machine scheduling p-roblem with controllable processing time of delivery and t-he workplece.According to the properties the optimal res-ource allocation method and the problem can be converte-d to assigment problem by construting a polynomial time ,Algorithm to detemine the optimal ordering and the learn-ing effect and problem with controllable processing times Respectively discusses the processing time is a linear res-ource functions and convex resource function in two case-sproved that this kind of problem is polynomial time solv-able finally discussed a special case study factor is consta-nt processing time is a convex resource function gives co-mplexity is O(nlog n)algorithm by running this algorithm .To detemine the optimal resource allocation optimal quan-tity and parts of the soft.
Key words:the single machine scheduling,delivery p-eriod,controllable processing times,resource allocation.
课题研究的目的意义和主要内容
排序又称调度,作为运筹学的一个分支,是一门应用性很强的学科,有着其深刻的实际背景和广泛的应用空间。在现代企业竞争中，准时生产已经成为一种重要的竞争策略。根据准时生产原则，工件的完工时间要尽量地靠近某一时刻（时间段）。如果工件在该时刻（时间段内）完工，就不会产生惩罚；如果工件在该时刻（时间段）之前或之后完工，就会产生提前或者延误的惩罚，这就是工期问题（工期窗口问题）。同时为提高机器的生产效率，可以考虑在机器上执行维修。本文主要讨论的是带有交货期和加工时间可控的单机排序问题，问题如下：
首先，第一章介绍有关排序问题的预备知识、相关问题的研究现状。第二章中，主要讨论了带有交货期和工件的加工时间可控的单机排序问题。其中，工件的加工时间是其资源分配的线性非增函数，并且分配资源会产生费用，目标函数是极小化总完工时间、提前时间、延误时间、工期窗口的结束时间以及资源分配的总费用。我们证明了该问题可以转化为指派问题，即该问题是多项式时间可解的。第三章讨论带有交货期和加工时间可控的单机排序问题的仿真。主要讨论使用软件进行单机排序问题仿真的结果。工件的实际加工时间是关于工件的开工时间、工件的位置以及资源分配的函数。目标给出了最优排序的一些性质及最优资源分配的求解方法、多项式算法，证明了这些问题在多项式时间内可以求得最优解。最后，对本文的主要结果进行总结，并提出将来的研究方向。
只有一台处理机作业的排序问题我们称之为单处理机(singleprOCessor)排序问题，又称单机排序间题，否则称为多处理机问题。在多处理机排序问题中，如果所有的处理机都具有相同的功能，称它们为平行机(parallelproCessors)。平行机按处理的速度又可以分为三种类型：同型机(identicalprocessor)、同类机(uniformproeessors)和不相关机(unrelatedproeessors)。
在下面文章中主要涉及的是单机排序问题。
摘 要………………………………………………………………………………………………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 |
