机器发生故障的排序问题

机器发生故障的排序问题

摘  要

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

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

目  录

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