機器發生故障的排序問題

信息計算科學論文編號: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