信息计算科学论文编号:XXLW098 论文字数:16371,页数:31

目  录
摘  要 i
Abstract ii
目  录 iii
前言 v
第一章  绪论 1
 1.1  排序问题 1
1.1.1 排序问题的基本概念 1
1.1.2 排序问题的表示法 2
1.1.3 排序问题的特点 4
 1.2  排序问题的研究历史 5
 1.3  现代排序的分类 6
1.3.1 可控排序 6
1.3.2 成组分批排序 7
1.3.3 在线排序 7
1.3.4 同时加工排序 8
1.3.5 准时排序和窗时排序 8
1.3.6 机器不同时开工排序 9
1.3.7 资源受限排序 9
1.3.8 随机排序 9
1.3.9 模糊排序 9
1.3.10 多目标排序 10
 1.4  排序问题的算法 10
1.4.1 近似算法(approximation algorithm) 10
1.4.2 启发式算法(heuristic algorithm) 11
第二章  误工任务数问题 12
 2.1问题 12
 2.2问题 12
2.2.1问题 13
2.2.2问题 13
 2.3 问题 14
2.3.1问题算法 14
2.3.2问题举例 15
2.3.3问题算法 15
2.3.3问题举例 15
第三章  总完工时间问题 15
 3.1  问题 15
3.1.1 SPT算法 15
3.1.2 问题举例 15
 3.2  问题 15
3.2.1 算法 15
3.2.2 问题举例 15
 3.3 问题 15
3.3.1 算法 15
3.3.2 问题举例 15
第四章 总结 15
致谢 15
参考文献 15

摘  要
 排序论作为运筹学的一个分支，有着深刻的实际背景和广阔的应用前景，它被广泛应用于管理科学、计算机科学和工程技术等领域。排序问题就是利用一些处理机、机器或者资源，最优的完成一批给定的任务（作业）。由于受到处理机，资源等条件的限制，排序问题可以分为多种排序问题。本文研究的是三台机器在其中一台发生故障情况下的重新排序问题。我们仅对目标函数为误工任务数和总完工时间进行研究，当故障发生时分考虑跨越工件的转移时间和不考虑跨越工件的转移时间两种情况。当考虑跨越工件的转移时间时，对跨越工件进行讨论，得到两种不同的排序方法，比较两者得到最优；当不考虑跨越工件的转移时间时，进行类似分析。并分别对得到的算法进行举例说明。

关键词：排序  最小化误工工件数  最小化总完工时间  机器带故障中断

Abstract
 Scheduling problem as a part of operations research, has deep practical background and broad application prospects. It is widely used in management science, computer science and engineering technology etc. Scheduling problem is to use a number of processors, machines or resources,completed a number of tasks or jobs in optimal way. As a result of being bound by processors, resources etc., scheduling problem is divided into many types. In the paper, we will discuss the rescheduling problem in which one of the three machine will break down. We just discuss the objective of functions just are minimizing the sum of number of tardy tasks and completion time. When the interrupt occurs, the problem is divided into considers the transfer time and does not consider the transfer time. If we consider the transfer time ,discussion of the work of the ongoing, we can get two different sort, compare the two to get the optimal. And if we do not consider the transfer time, we will conduct a similar analysis. We also examples to explain the optimal scheduling and algorithms.
  
Keywords: scheduling; minimizing the sum of unit penalties; minimizing the sum of completion time; machine disruptions