多約束復雜工作流的調度優(yōu)化.pdf

1、項目調度是廣泛存在于生產(chǎn)制造、工業(yè)工程、計算機等系統(tǒng)的重要問題，項目各活動間的偏序關系、截止期等多種約束使得該類問題為典型的NP難問題。本文考慮有限可用資源的單一加工方式生產(chǎn)調度、可中斷加工項目調度、多模態(tài)資源約束項目調度、具有準備時間和截止期約束的云工作流調度等問題，分析相應問題的特點，建立數(shù)學模型，提出有效的算法，為實際生產(chǎn)應用提供決策支持。論文的主要工作體現(xiàn)在:
　　(1)不可中斷單模態(tài)資源約束項目調度優(yōu)化。建立最小化完工時

2、間的不可中斷單模態(tài)資源約束項目調度問題數(shù)學模型;將原問題分解為兩個子問題:活動調度順序確定和調度生成;提出改進粒子群算法優(yōu)化活動序列，提出快速調度方法確定給定排列順序下的活動開始時間，生成有效的調度方案。實驗結果表明，本文所提方法可以為項目找到近似最優(yōu)的調度方案，是有效解決該問題的方法之一。
　　(2)可中斷單模態(tài)資源約束項目調度優(yōu)化。分析活動可中斷加工模式對提高生產(chǎn)效率的影響，構建最小化完工時間的可中斷資源約束項目調度問題模型;

3、將允許一次中斷的調度問題中的每個活動分成加工長度可動態(tài)調整的兩個子活動，提出遺傳算法優(yōu)化活動調度順序和子活動加工長度;提出基于資源管理鏈表的調度生成方法，根據(jù)資源可用情況動態(tài)調整各子活動加工長度。實驗結果表明，在資源有限情況下允許活動可中斷可以縮短項目完工時間。
　　(3)多模態(tài)資源約束項目調度優(yōu)化?？紤]活動在多種加工模式下對資源需求和加工長度的不同，建立最小化完工時間的多模態(tài)資源約束項目調度問題的模型;將原問題分解為三個子問題:

4、模式分配、活動排序和調度生成;提出離散的粒子群優(yōu)化方法，采用兩個協(xié)作群分別求解模式分配問題和活動排序問題，獲得最優(yōu)模式分配方案和最優(yōu)活動序列，提出局部搜索策略進一步改善算法局部優(yōu)化能力;設計正向/反向改進的調度生成方法。實驗結果表明，兩群協(xié)作優(yōu)化方法可以找到問題的近似最優(yōu)解，是求解該問題的有效方法。
　　(4)云制造環(huán)境下具有準備時間和截止期約束工作流調度優(yōu)化。根據(jù)云環(huán)境中資源的分散性和用戶不同的截止期約束，以最小化工作流費用為目