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

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

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

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

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