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

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

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

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

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