掃一掃
關注中圖網
官方微博
本類五星書更多>
-
>
蜜蜂的寓言:私人的惡德,公眾的利益
-
>
世界貿易戰簡史
-
>
日本的凱恩斯:高橋是清傳:從足輕到藏相
-
>
近代天津工業與企業制度
-
>
貨幣之語
-
>
眉山金融論劍
-
>
圖解資本論
第三類產品制造調度模式——綜合調度 版權信息
- ISBN：9787030752253
- 條形碼：9787030752253 ; 978-7-03-075225-3
- 裝幀：一般膠版紙
- 冊數：暫無
- 重量：暫無
- 所屬分類：>
第三類產品制造調度模式——綜合調度 內容簡介
為了提高單件復雜產品或多品種小批量產品制造效率，作者謝志強經過多年研究，于2009年提出繼產品加工調度和產品裝配調度之后的第三類產品制造調度模式：加工和裝配一同處理的綜合調度。本專著整理了作者多年的研究成果，按綜合調度解決的大問題分類，即一般綜合調度篇、特殊產品綜合調度篇和特殊設備綜合調度篇；在每篇中按問題的特點和解決次序排序，系統介紹了綜合調度研究的發展過程、作用和應用，從綜合調度研究的深度、廣度上和應用領域上為有興趣研究綜合調度的人員提供了系統、全方位的參考。
第三類產品制造調度模式——綜合調度 目錄
目錄
《信息科學技術學術著作叢書》序
前言
一般綜合調度篇
第1章 綜合調度基本概念介紹 3
1.1 引言 3
1.2 相關和獨立工序調度的數學描述 3
1.3 工序分類與分析 4
1.3.1 相關工序 4
1.3.2 獨立工序 4
1.4 分類排序*優性分析 4
1.5 擬關鍵路徑法和*佳適應調度算法 5
1.5.1 擬關鍵路徑法 5
1.5.2 *佳適應調度算法 6
1.6 算法實現及復雜度分析 6
1.6.1 算法實現 6
1.6.2 排序算法復雜性 7
1.6.3 復雜度分析 9
1.6.4 實例分析 11
1.7 本章小結 15
第2章 可動態生成具有優先級工序集的單產品綜合調度算法 16
2.1 引言 16
2.2 單產品綜合問題描述 16
2.3 單產品綜合調度問題分析 17
2.4 調度策略設計 17
2.4.1 優先級調度策略 17
2.4.2 短用時調度策略 19
2.4.3 長路徑調度策略 20
2.4.4 動態調整調度策略 21
2.5 算法設計 23
2.6 算法復雜度分析 23
2.7 實例分析 23
2.8 本章小結 24
第3章 關鍵設備工序緊湊的綜合調度算法 25
3.1 引言 25
3.2 工序分類與分析 25
3.2.1 產品加工工藝樹的分析 25
3.2.2 加工工藝樹的分解及工序加工的優先級 26
3.2.3 分類排序*優性分析 27
3.3 分類排序的描述 27
3.4 關鍵設備上的工序盡量緊湊法 27
3.5 考慮關鍵設備的調度算法 28
3.5.1 考慮關鍵設備的擬關鍵路徑法 28
3.5.2 *佳適應調度算法 29
3.5.3 排序非關鍵分支上的工序 30
3.5.4 其他產品 30
3.6 算法實現及復雜度分析 30
3.7 實例分析 32
3.8 本章小結 35
第4章 多設備緊湊的復雜產品調度優化算法 36
4.1 引言 36
4.2 ACPM和關鍵設備緊湊算法簡介 36
4.2.1 ACPM簡介 36
4.2.2 關鍵設備緊湊算法簡介 36
4.3 多設備緊湊算法描述 37
4.3.1 空閑時間段拉伸條件的確定 37
4.3.2 調整約束關系被破壞的工序位置 38
4.4 多設備緊湊算法的設計 38
4.5 多設備緊湊算法分析 39
4.6 實例分析 40
4.7 本章小結 44
第5章 考慮工序前移的多設備緊湊優化調整策略 45
5.1 引言 45
5.2 工序前移調整策略描述 45
5.3 空閑時間段拉伸條件的確定 45
5.4 調整約束關系被破壞的工序位置 46
5.5 加入工序前移調整策略的算法設計 46
5.6 加入工序前移調整策略的算法分析 47
5.7 實例分析 48
5.8 本章小結 52
第6章 考慮無縫拉伸的多設備緊湊優化調整策略 53
6.1 引言 53
6.2 無縫拉伸調整策略描述 53
6.3 空閑時間段拉伸條件的確定 53
6.4 調整約束關系被破壞的工序位置 54
6.5 加入無縫拉伸調整策略的算法設計 54
6.6 加入無縫拉伸調整策略的算法分析 55
6.7 實例分析 56
6.8 本章小結 59
第7章 基于調度長路徑的復雜產品綜合調度算法 60
7.1 引言 60
7.2 問題描述 60
7.3 調度策略與算法設計 61
7.3.1 工序調度策略設計與分析 61
7.3.2 調度算法設計 62
7.4 算法復雜度分析 62
7.5 實例分析 64
7.6 本章小結 67
第8章 復雜產品縱橫雙向綜合調度優化算法 69
8.1 引言 69
8.2 問題描述 69
8.3 調度策略分析與設計 70
8.4 算法設計 71
8.5 算法復雜度分析 72
8.6 實例分析 73
8.7 本章小結 76
第9章 基于工序集的動態關鍵路徑多產品制造調度算法 77
9.1 引言 77
9.2 問題描述 77
9.3 問題分析 78
9.3.1 加工工藝樹 78
9.3.2 工序類型分類 78
9.4 調度策略設計 78
9.4.1 動態關鍵路徑策略 79
9.4.2 短用時策略 80
9.5 算法設計 80
9.6 算法復雜度分析 81
9.7 實例分析 82
9.8 本章小結 84
第10章 基于動態實質短路徑的綜合調度算法 85
10.1 引言 85
10.2 復雜單產品綜合調度優化問題描述 85
10.3 復雜單產品綜合調度優化問題分析 86
10.4 綜合調度優化策略設計 86
10.5 復雜單產品綜合調度優化算法設計 88
10.6 算法復雜度分析 91
10.7 實例分析 92
10.8 本章小結 95
第11章 基于動態實質路徑結束時間的綜合調度算法 97
11.1 引言 97
11.2 問題模型描述 97
11.3 調度策略分析及設計 98
11.3.1 動態早結束實質路徑策略 99
11.3.2 早結束實質路徑不唯一時工序優先策略 100
11.4 動態確定可調度工序的開始時間 101
11.4.1 調整備選工序集中同設備工序的開始時間 101
11.4.2 確定新加入備選工序集中工序的開始時間 102
11.4.3 動態確定可調度工序開始時間策略的具體實現步驟 102
11.5 算法流程圖和復雜度分析 103
11.6 實例分析 105
11.7 本章小結 108
第12章 基于設備空閑事件驅動的綜合調度算法 110
12.1 引言 110
12.2 問題描述 110
12.3 事件驅動調度策略 111
12.4 *大并行性選擇策略與實現 111
12.5 設備驅動時刻算法與實現 114
12.6 實例分析 117
12.7 本章小結 119
第13章 可回退搶占的事件驅動綜合調度算法 120
13.1 引言 120
13.2 問題描述 120
13.3 回退事件分析與處理 122
13.3.1 工序搶占分析 122
13.3.2 回退策略可靠性分析 125
13.4 算法設計及復雜度分析 126
13.4.1 算法設計 126
13.4.2 復雜度分析 128
13.5 實例分析 129
13.6 本章小結 131
第14章 基于動態關鍵路徑的復雜多產品調度算法 132
14.1 引言 132
14.2 問題描述 132
14.3 問題分析 132
14.4 算法分析 134
14.5 算法設計 134
14.6 算法復雜度分析 134
14.7 實例分析 136
14.8 本章小結 138
第15章 開始時間和交貨期都不同的綜合調度算法 139
15.1 引言 139
15.2 問題描述 140
15.3 有時間限制的多品種小批量產品調度設計與分析 141
15.3.1 調度策略 141
15.3.2 優先級策略 141
15.3.3 長路徑策略 144
15.3.4 短用時策略 144
15.3.5 采用設備工序緊湊法確定工序開始時間 144
15.4 算法設計 145
15.5 算法復雜度分析 146
15.6 實例分析 148
15.7 本章小結 156
第16章 開始時間和交貨期都不同的改進綜合調度算法 157
16.1 引言 157
16.2 調度設計與分析 157
16.2.1 調度策略 157
16.2.2 確定有時間限制的多品種小批量產品的調度順序的策略分析 158
16.2.3 層優先策略 159
16.2.4 層優先長路徑策略 159
16.2.5 層優先短用時策略 160
16.3 算法分析 160
16.4 算法復雜度分析 161
16.5 實例分析 161
16.6 本章小結 166
第17章 確定復雜多產品調度順序的算法 167
17.1 引言 167
17.2 累計設備空閑段的調度算法 167
17.3 關鍵產品的確定 167
17.4 實例驗證及分析 169
17.4.1 實例驗證 169
17.4.2 算法分析 172
17.5 本章小結 172
第18章 動態累計設備空閑時間確定多產品調度順序的算法 173
18.1 引言 173
18.2 算法描述 173
18.3 算法設計及步驟 173
18.4 實例分析 174
18.5 本章小結 178
第19章 可動態生成具有優先級工序集的動態綜合調度算法 179
19.1 引言 179
19.2 動態綜合問題描述 179
19.3 動態綜合問題分析 179
19.4 算法設計 180
19.5 動態綜合調度問題算法流程圖 180
19.6 動態調度實例分析 182
19.7 本章小結 183
特殊產品綜合調度篇
第20章 非緊密銜接工序綜合調度問題的提出及調度策略 187
20.1 引言 187
20.2 非緊密銜接工序調度問題分析 187
20.3 非緊密銜接工序調度問題模型設計 189
20.3.1 工序分類 189
20.3.2 擴展加工工藝樹模型 189
20.4 非緊密銜接工序到緊密銜接工序的轉換策略 189
20.5 非緊密銜接工序調度算法的復雜度分析 190
20.6 實例分析 191
20.7 本章小結 193
第21章 非緊密銜接工序動態綜合調度算法 194
21.1 引言 194
21.2 非緊密銜接工序動態調度問題描述與分析 194
21.2.1 非緊密銜接工序動態調度問題描述 194
21.2.2 非緊密銜接工序分類 195
21.2.3 非緊密銜接工序調度問題建模 195
21.3 延遲約束轉換 195
21.4 擴展加工工藝樹的分解及工序加工的優先級 196
21.5 基于ACPM和BFSM的動態調度算法設計 197
21.5.1 基于擬關鍵路徑法的調度策略 197
21.5.2 基于*佳適應調度算法的調度策略 197
21.5.3 關鍵設備上的標準工序盡量緊湊法 197
21.5.4 非緊密銜接工序動態調度策略 198
21.6 非緊密銜接加工工序動態調度實例 198
21.7 本章小結 202
第22章 存在設備有關延遲約束的綜合調度算法 204
22.1 引言 204
22.2 問題分析與方案設計 204
22.2.1 工序分類 205
22.2.2 存在設備有關延遲約束的加工工藝樹模型設計 205
22.3 等待延遲時間到設備有關延遲工序的轉換策略 206
22.4 算法設計 207
22.4.1 擬關鍵路徑法 208
22.4.2 工序調度算法分析 208
22.5 存在設備有關延遲約束的綜合調度算法的實現 209
22.6 存在設備有關延遲約束的綜合調度算法的復雜度分析 209
22.7 實例分析 210
22.8 本章小結 213
第23章 工序間存在零等待約束的復雜產品調度算法 214
23.1 引言 214
23.2 復雜產品調度問題分析 214
23.3 復雜產品調度問題研究 215
23.4 算法設計 216
23.4.1 算法描述 216
23.4.2 移動交換算法流程圖 219
23.5 算法復雜度分析 220
23.6 實例分析 220
23.7 本章小結 222
第24章 工序間存在零等待約束的復雜產品動態調度算法 223
24.1 引言 223
24.2 動態調度問題分析 223
24.3 動態調度算法流程圖 224
24.4 算法復雜度分析 225
24.5 實例分析 225
24.6 本章小結 227
第25章 緊密銜接工序組聯動的綜合調度算法 228
25.1 引言 228
25.2 問題描述 228
25.3 調度策略分析與設計 229
25.4 確定復雜產品工序調度順序的算法 229
25.4.1 確定工序組及其相關工序的調度順序 229
25.4.2 使用擬關鍵路徑法確定剩余標準工序的調度順序 230
25.4.3 復雜產品工序調度順序算法的實現說明 230
25.5 確定工序在設備上的調度加工 232
25.5.1 使用首次適應調度算法加工標準工序 232
25.5.2 使用首次適應調度算法加工工序組中工序 232
25.5.3 復雜產品工序在設備上
《信息科學技術學術著作叢書》序
前言
一般綜合調度篇
第1章 綜合調度基本概念介紹 3
1.1 引言 3
1.2 相關和獨立工序調度的數學描述 3
1.3 工序分類與分析 4
1.3.1 相關工序 4
1.3.2 獨立工序 4
1.4 分類排序*優性分析 4
1.5 擬關鍵路徑法和*佳適應調度算法 5
1.5.1 擬關鍵路徑法 5
1.5.2 *佳適應調度算法 6
1.6 算法實現及復雜度分析 6
1.6.1 算法實現 6
1.6.2 排序算法復雜性 7
1.6.3 復雜度分析 9
1.6.4 實例分析 11
1.7 本章小結 15
第2章 可動態生成具有優先級工序集的單產品綜合調度算法 16
2.1 引言 16
2.2 單產品綜合問題描述 16
2.3 單產品綜合調度問題分析 17
2.4 調度策略設計 17
2.4.1 優先級調度策略 17
2.4.2 短用時調度策略 19
2.4.3 長路徑調度策略 20
2.4.4 動態調整調度策略 21
2.5 算法設計 23
2.6 算法復雜度分析 23
2.7 實例分析 23
2.8 本章小結 24
第3章 關鍵設備工序緊湊的綜合調度算法 25
3.1 引言 25
3.2 工序分類與分析 25
3.2.1 產品加工工藝樹的分析 25
3.2.2 加工工藝樹的分解及工序加工的優先級 26
3.2.3 分類排序*優性分析 27
3.3 分類排序的描述 27
3.4 關鍵設備上的工序盡量緊湊法 27
3.5 考慮關鍵設備的調度算法 28
3.5.1 考慮關鍵設備的擬關鍵路徑法 28
3.5.2 *佳適應調度算法 29
3.5.3 排序非關鍵分支上的工序 30
3.5.4 其他產品 30
3.6 算法實現及復雜度分析 30
3.7 實例分析 32
3.8 本章小結 35
第4章 多設備緊湊的復雜產品調度優化算法 36
4.1 引言 36
4.2 ACPM和關鍵設備緊湊算法簡介 36
4.2.1 ACPM簡介 36
4.2.2 關鍵設備緊湊算法簡介 36
4.3 多設備緊湊算法描述 37
4.3.1 空閑時間段拉伸條件的確定 37
4.3.2 調整約束關系被破壞的工序位置 38
4.4 多設備緊湊算法的設計 38
4.5 多設備緊湊算法分析 39
4.6 實例分析 40
4.7 本章小結 44
第5章 考慮工序前移的多設備緊湊優化調整策略 45
5.1 引言 45
5.2 工序前移調整策略描述 45
5.3 空閑時間段拉伸條件的確定 45
5.4 調整約束關系被破壞的工序位置 46
5.5 加入工序前移調整策略的算法設計 46
5.6 加入工序前移調整策略的算法分析 47
5.7 實例分析 48
5.8 本章小結 52
第6章 考慮無縫拉伸的多設備緊湊優化調整策略 53
6.1 引言 53
6.2 無縫拉伸調整策略描述 53
6.3 空閑時間段拉伸條件的確定 53
6.4 調整約束關系被破壞的工序位置 54
6.5 加入無縫拉伸調整策略的算法設計 54
6.6 加入無縫拉伸調整策略的算法分析 55
6.7 實例分析 56
6.8 本章小結 59
第7章 基于調度長路徑的復雜產品綜合調度算法 60
7.1 引言 60
7.2 問題描述 60
7.3 調度策略與算法設計 61
7.3.1 工序調度策略設計與分析 61
7.3.2 調度算法設計 62
7.4 算法復雜度分析 62
7.5 實例分析 64
7.6 本章小結 67
第8章 復雜產品縱橫雙向綜合調度優化算法 69
8.1 引言 69
8.2 問題描述 69
8.3 調度策略分析與設計 70
8.4 算法設計 71
8.5 算法復雜度分析 72
8.6 實例分析 73
8.7 本章小結 76
第9章 基于工序集的動態關鍵路徑多產品制造調度算法 77
9.1 引言 77
9.2 問題描述 77
9.3 問題分析 78
9.3.1 加工工藝樹 78
9.3.2 工序類型分類 78
9.4 調度策略設計 78
9.4.1 動態關鍵路徑策略 79
9.4.2 短用時策略 80
9.5 算法設計 80
9.6 算法復雜度分析 81
9.7 實例分析 82
9.8 本章小結 84
第10章 基于動態實質短路徑的綜合調度算法 85
10.1 引言 85
10.2 復雜單產品綜合調度優化問題描述 85
10.3 復雜單產品綜合調度優化問題分析 86
10.4 綜合調度優化策略設計 86
10.5 復雜單產品綜合調度優化算法設計 88
10.6 算法復雜度分析 91
10.7 實例分析 92
10.8 本章小結 95
第11章 基于動態實質路徑結束時間的綜合調度算法 97
11.1 引言 97
11.2 問題模型描述 97
11.3 調度策略分析及設計 98
11.3.1 動態早結束實質路徑策略 99
11.3.2 早結束實質路徑不唯一時工序優先策略 100
11.4 動態確定可調度工序的開始時間 101
11.4.1 調整備選工序集中同設備工序的開始時間 101
11.4.2 確定新加入備選工序集中工序的開始時間 102
11.4.3 動態確定可調度工序開始時間策略的具體實現步驟 102
11.5 算法流程圖和復雜度分析 103
11.6 實例分析 105
11.7 本章小結 108
第12章 基于設備空閑事件驅動的綜合調度算法 110
12.1 引言 110
12.2 問題描述 110
12.3 事件驅動調度策略 111
12.4 *大并行性選擇策略與實現 111
12.5 設備驅動時刻算法與實現 114
12.6 實例分析 117
12.7 本章小結 119
第13章 可回退搶占的事件驅動綜合調度算法 120
13.1 引言 120
13.2 問題描述 120
13.3 回退事件分析與處理 122
13.3.1 工序搶占分析 122
13.3.2 回退策略可靠性分析 125
13.4 算法設計及復雜度分析 126
13.4.1 算法設計 126
13.4.2 復雜度分析 128
13.5 實例分析 129
13.6 本章小結 131
第14章 基于動態關鍵路徑的復雜多產品調度算法 132
14.1 引言 132
14.2 問題描述 132
14.3 問題分析 132
14.4 算法分析 134
14.5 算法設計 134
14.6 算法復雜度分析 134
14.7 實例分析 136
14.8 本章小結 138
第15章 開始時間和交貨期都不同的綜合調度算法 139
15.1 引言 139
15.2 問題描述 140
15.3 有時間限制的多品種小批量產品調度設計與分析 141
15.3.1 調度策略 141
15.3.2 優先級策略 141
15.3.3 長路徑策略 144
15.3.4 短用時策略 144
15.3.5 采用設備工序緊湊法確定工序開始時間 144
15.4 算法設計 145
15.5 算法復雜度分析 146
15.6 實例分析 148
15.7 本章小結 156
第16章 開始時間和交貨期都不同的改進綜合調度算法 157
16.1 引言 157
16.2 調度設計與分析 157
16.2.1 調度策略 157
16.2.2 確定有時間限制的多品種小批量產品的調度順序的策略分析 158
16.2.3 層優先策略 159
16.2.4 層優先長路徑策略 159
16.2.5 層優先短用時策略 160
16.3 算法分析 160
16.4 算法復雜度分析 161
16.5 實例分析 161
16.6 本章小結 166
第17章 確定復雜多產品調度順序的算法 167
17.1 引言 167
17.2 累計設備空閑段的調度算法 167
17.3 關鍵產品的確定 167
17.4 實例驗證及分析 169
17.4.1 實例驗證 169
17.4.2 算法分析 172
17.5 本章小結 172
第18章 動態累計設備空閑時間確定多產品調度順序的算法 173
18.1 引言 173
18.2 算法描述 173
18.3 算法設計及步驟 173
18.4 實例分析 174
18.5 本章小結 178
第19章 可動態生成具有優先級工序集的動態綜合調度算法 179
19.1 引言 179
19.2 動態綜合問題描述 179
19.3 動態綜合問題分析 179
19.4 算法設計 180
19.5 動態綜合調度問題算法流程圖 180
19.6 動態調度實例分析 182
19.7 本章小結 183
特殊產品綜合調度篇
第20章 非緊密銜接工序綜合調度問題的提出及調度策略 187
20.1 引言 187
20.2 非緊密銜接工序調度問題分析 187
20.3 非緊密銜接工序調度問題模型設計 189
20.3.1 工序分類 189
20.3.2 擴展加工工藝樹模型 189
20.4 非緊密銜接工序到緊密銜接工序的轉換策略 189
20.5 非緊密銜接工序調度算法的復雜度分析 190
20.6 實例分析 191
20.7 本章小結 193
第21章 非緊密銜接工序動態綜合調度算法 194
21.1 引言 194
21.2 非緊密銜接工序動態調度問題描述與分析 194
21.2.1 非緊密銜接工序動態調度問題描述 194
21.2.2 非緊密銜接工序分類 195
21.2.3 非緊密銜接工序調度問題建模 195
21.3 延遲約束轉換 195
21.4 擴展加工工藝樹的分解及工序加工的優先級 196
21.5 基于ACPM和BFSM的動態調度算法設計 197
21.5.1 基于擬關鍵路徑法的調度策略 197
21.5.2 基于*佳適應調度算法的調度策略 197
21.5.3 關鍵設備上的標準工序盡量緊湊法 197
21.5.4 非緊密銜接工序動態調度策略 198
21.6 非緊密銜接加工工序動態調度實例 198
21.7 本章小結 202
第22章 存在設備有關延遲約束的綜合調度算法 204
22.1 引言 204
22.2 問題分析與方案設計 204
22.2.1 工序分類 205
22.2.2 存在設備有關延遲約束的加工工藝樹模型設計 205
22.3 等待延遲時間到設備有關延遲工序的轉換策略 206
22.4 算法設計 207
22.4.1 擬關鍵路徑法 208
22.4.2 工序調度算法分析 208
22.5 存在設備有關延遲約束的綜合調度算法的實現 209
22.6 存在設備有關延遲約束的綜合調度算法的復雜度分析 209
22.7 實例分析 210
22.8 本章小結 213
第23章 工序間存在零等待約束的復雜產品調度算法 214
23.1 引言 214
23.2 復雜產品調度問題分析 214
23.3 復雜產品調度問題研究 215
23.4 算法設計 216
23.4.1 算法描述 216
23.4.2 移動交換算法流程圖 219
23.5 算法復雜度分析 220
23.6 實例分析 220
23.7 本章小結 222
第24章 工序間存在零等待約束的復雜產品動態調度算法 223
24.1 引言 223
24.2 動態調度問題分析 223
24.3 動態調度算法流程圖 224
24.4 算法復雜度分析 225
24.5 實例分析 225
24.6 本章小結 227
第25章 緊密銜接工序組聯動的綜合調度算法 228
25.1 引言 228
25.2 問題描述 228
25.3 調度策略分析與設計 229
25.4 確定復雜產品工序調度順序的算法 229
25.4.1 確定工序組及其相關工序的調度順序 229
25.4.2 使用擬關鍵路徑法確定剩余標準工序的調度順序 230
25.4.3 復雜產品工序調度順序算法的實現說明 230
25.5 確定工序在設備上的調度加工 232
25.5.1 使用首次適應調度算法加工標準工序 232
25.5.2 使用首次適應調度算法加工工序組中工序 232
25.5.3 復雜產品工序在設備上
展開全部
第三類產品制造調度模式——綜合調度 節選
一般綜合調度篇 第1章綜合調度基本概念介紹 1.1引言 由于車間調度問題(job-shopschedulingproblem，JSSP)在產品數大于2時是NPC(non-deterministicpolynomialcomplete)問題[1]，人們提出許多近優解方案[2，3]。本書對綜合調度問題只存在唯一緊前、緊后相關工序和獨立工序兩類工序時，結合操作系統中內存調度的*佳適應(bestfit，BF)調度方法和首次適應(firstfit，FF)調度方法的先進思想[4]，提出一種全新近優解方案，即對這兩類工序分批采用擬關鍵路徑法(alliedcriticalpathmethod，ACPM)和*佳適應調度算法(bestfitschedulingmethod，BFSM)安排工序，并以實例加以驗證。分析和實驗表明，該方法不但約束條件少，有較令人滿意的算法復雜度，而且*優效果好。 1.2相關和獨立工序調度的數學描述 設有k個產品，每個產品的工序數為，則總工序數為。 在m個設備上加工產品，要求滿足以下條件。 ①一臺設備在某一時刻只能加工一道工序。 ②一道工序在某一時刻只能被一臺設備加工。 ③一臺設備一旦加工某道工序，則直到該工序完成加工，這臺設備才能加工其他工序。 ④每道工序都必須在其緊前工序加工完成后，才能開始。 ⑤當上一道工序加工完后，立即送下一道工序加工。 ⑥每道工序的加工時間已知，并且與加工順序無關。 ⑦允許工序之間等待，允許設備在工序達到之前閑置。 除*后工序外，假設加工的產品只有唯一緊前、緊后相關工序和獨立工序。由于產品*后工序的開始加工時間必須等其前面的相關工序和獨立工序加工完畢，因此產品加工時間主要受其*后工序前的唯一緊前、緊后相關工序和獨立工序全部加工完畢時間的影響。在*后工序加工時間不計的情況下，k個產品全部加工完畢的時間為給定約束條件下的*短值，即 (1-1) (1-2) (1-3) (1-4) 式中，為設備的第個工序的開始加工時間；為設備i的第j個工序的連續加工時間。 1.3工序分類與分析 當只存在具有唯一緊前、緊后相關工序和獨立工序兩類工序時，以往調度方法都是不分工序的種類，一并考慮排序。 事實上，將兩類工序分別采用不同的排序方法，不但可以在排序方法上得到互補，而且可以充分考慮工序在設備上加工的并行性，即提高設備的利用率，縮短產品加工的總時間。 1.3.1相關工序 雖然具有唯一緊前、緊后相關工序開始加工的時間有嚴格的約束，但是不同的相關工序序列加工是并行的。由于各相關工序序列一般包含多個工序且加工總時間相對較長，因此加工總時間越長，相關工序序列對全部產品加工總時間的影響越大。但是，其靈活性卻很差，所以只有將加工總時間長的相關工序序列優先排序，才能將相關工序排序總的調整時間段控制到*少。如果有加工總時間長度相同的相關工序序列，則優先排序相關工序數多的相關工序序列。這不但可以減少排序總時間，而且可以減少所有相關工序的加工總時間。 1.3.2獨立工序 在不考慮產品*后工序的情況下，本書將不存在緊前工序或緊后工序的工序稱為獨立工序。嚴格地說，產品加工無獨立工序。 獨立工序的加工特點是不但可并行、時間短，而且沒有工序開始加工的時間約束，因此具有很強的靈活性。 1.4分類排序*優性分析 分類排序的*大優點是充分考慮工序在設備上加工的并行性，將兩類工序排序優勢互補，既考慮相關工序對全部產品加工總時間的影響，又考慮獨立工序的靈活性。 利用各相關工序序列與各獨立工序在設備上加工的并行性，按工序連續加工時間的長短安排設備既可以優先安排加工總時間長的相關工序序列，又可以讓靈活性強的短工序序列與各獨立工序根據實際情況插入工序排序過程中形成的時間空隙段，提高各設備的利用率。 總的來說，分類排序是先分類，再綜合排序，以實現快速、全部工序加工總時間盡可能少為目標。 1.5擬關鍵路徑法和*佳適應調度算法 1.5.1擬關鍵路徑法 根據*優關鍵路徑法定理，關鍵路徑若不包含塊，則一定是*優解[3]。因此，首先將相關工序序列連續加工總時間分別求出，按總時間由長到短排序。如果有加工總時間長度相同的相關工序序列，則優先排序相關工序數多的相關工序序列。其次，將總時間*長的相關工序序列按工序加工時間和順序分配給相關設備，即形成工序排序初始關鍵路徑。再次，分配總時間第二長的相關工序序列，按工序序列順序將各工序插入，并使工序盡早完工，直到全部相關工序序列都分配給相關設備。*后，根據相關工序的分析，研究應用ACPM。 ①將所有相關工序構成三維數組W=[wijk]I*J*M，其中I為各序列按總時間由長到短排序好的相關工序序列數，如果有加工總時間長度相同的相關工序序列，則優先排序相關工序數多的相關工序序列；J為各相關工序序列中工序數*大值；M為設備數。 ②設與相關工序數組相應的工序連續加工時間數組為，工序開始時間數組為E=[eijk]I*J*M。 ③相關工序加工排序要求。 ④按對**序列排序，并將安排的工序按設備加工排序，表示第k臺設備上第n個加工工序的開始時間，表示第k臺設備上第n個加工工序的連續加工時間。具體實現方法如下。 **，對下標i賦值i←1。 第二，因為設備初始時無工序，所以n←0。 第三，如果工序屬于第臺設備，即。 第四，循環執行第三步，直到**相關序列上的工序排完。 第五，順序排列其他序列，按及下面的約束條件排序。 其一，如果設備已排工序間無法安排新增工序，將其排在設備kx已排工序的*后，即，則。 其二，如果設備已排工序和之間可安排新增工序，即.則設備上第個及以后的已排工序后移，將插入合適的空閑段。 其三，循環執行上述兩步，直到工序排完。 1.5.2*佳適應調度算法 將獨立工序按對應設備插入由ACPM形成的工序加工排列中，為了提高各設備利用率，即縮短各設備完工時間，插入對應設備的獨立工序時，可以采用BFSM將設備的各閑置時間段控制到*短，即無法安排尚未插入的獨立工序[4]。為了更好地實現BFSM，具體方法如下。 ①將各設備的獨立工序按加工時間由長到短排序，令表示獨立工序按加工時間由長到短排序后，第k臺設備上第n個獨立工序的加工時間，其開始時間為，因此有。 ②對排序的各設備工序，將**個獨立工序的加工時間與該設備各閑置時間段從前到后進行比較。 ③采用FF調度算法[4]，對**個滿足閑置時間段大于等于加工時間的工序，將其插入該閑置時間段。此工序開始加工時間緊接該閑置時間段前的工序完工時間。 **，如果設備k已排工序間無法安排新增工序，將排在設備k已排工序的*后，即，則。 第二，如果設備k已排工序n和n+1之間可安排新增工序，即.則設備k上第n+1個及以后已排的工序后移，將插入合適的空閑段。 ④循環執行②和③，直到各設備的獨立工序全部插入。 1.6算法實現及復雜度分析 1.6.1算法實現 結合相關工序序列的ACPM和獨立工序的BFSM。算法實現的程序流程圖如圖1-1所示。
書友推薦
- >
詩經-先民的歌唱
- >
中國人在烏蘇里邊疆區:歷史與人類學概述
- >
羅曼·羅蘭讀書隨筆-精裝
- >
月亮與六便士
- >
自卑與超越
- >
我與地壇
- >
上帝之肋:男人的真實旅程
- >
人文閱讀與收藏·良友文學叢書:一天的工作
本類暢銷
