带有交货期和加工时间可控的单机排序问题

一、题目

    带有交货期和加工时间可控的单机排序问题

二、指导思想和目的要求

    文档设计（范文）是培养学生自学能力、综合应用能力、独立工作能力的重要教学实践环节。

    在文档设计中，学生应独立承担一部分比较完整的工程技术设计任务。要求学生发挥主观能动性，积极性和创造性，在文档设计中着重培养独立工作能力和分析解决问题的能力，严谨踏实的工作作风，理论联系实际，以严谨认真的科学态度，进行有创造性的工作，认真、按时完成任务。

三、主要技术指标

1、优化数学模型；

2、算法的优化程序；

3、仿真程序；

4、仿真验证结果；

5、设计说明书一份；

四、进度和要求

第01周----第02周： 撰写文档设计开题报告；

第03周----第04周： 文献翻译；

第05周----第06周： 分析并确定优化的目标函数，根据约束条件建立优化数学模型 ；

第07周----第09周： 编制算法的优化程序；

第10周----第11周：学习使用软件，设计相应的调度方案；

第12周----第13周： 搭建仿真程序，进行仿真、验证；

第14周----第16周： 撰写文档设计范文，范文答辩。

五、主要参考书及参考资料

[1]范雁鹏、赵传立.带有交货期和加工时间可控的单机排序问题.沈阳师范大学 数学与系统科学学院，沈阳110034.

[2] 何燕.基于遗传算法的车间调度优化及其仿真.武汉理工大学.2006

[3] 欧阳珍.基于遗传算法的车间调度研究与应用.浙江大学.2004.

[4]何少龙.具有安装时间和变量加工时间的单机排序问题.2011.

[5] 潘全科.智能制造系统多目标车间调度研究.南京航空航天大学.2003.

[6]Michael Pinedo(美).调度：原理、算法和系统（第二版）.清华大学出版社.

[7] 薛家兵、鄂明成.基于Flexsim仿真的FMS车间级控制开发系统.北京交通大学.机械与电子控制工程学院.北京.100044.2007.

[8]唐恒永.赵传立.排序引论[M].北京：科学出版社.

[9]Mor B，Mosheiov G.Scheduling a maintenance activity and due-window assignment based on commom flow allowance[J].International Jouranl of Production Economics.2012.135(1):220-230.

[10] Hsu C J,Yang S J,Yang D L. Two due date assignment problems with position- dependent  processing  time  on  a  single-machine[J]. Computers &  Industrial Engineering,2011,60(4):796–800. 

[11] Cheng T C E, Oguz C,Qi X D. Due-date assignment for scheduling on a single machine  with compressible processing time[J].Internatio

nal Journal of Production Economics.1996,43(2):107-113.

[12] Shabtay D, Steiner G. The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times[J]. Annals of Operations Research,2008,159(1):25-40.

带有交货期和加工时间可控的单机排序问题

 摘要  

 

    排序问题是一类重要的组合最优化问题。排序问题普遍应用于管理等学科领域，是组合最优化的一类重要问题。调度的任务是根据生产目标和约束，为每个加工对象确定具体的加工路线、时间、机器和操作等。优良的调度策略对于提高生产系统的最优性、提高经济效益都有着极大的作用。但是由于资源约束和工艺约束的并存，迄今计算复杂性理论表明，多数调度问题属于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.

带有交货期和加工时间可控的单机排序问题

摘 要………………………………………………………………………………………………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