若干單件訂單接受與加工調(diào)度問題及其優(yōu)化方法研究.pdf

1、面對眾多的單件訂單及其不同的交貨期要求，如何在加工資源有限的情況下同時(shí)進(jìn)行單件訂單接受優(yōu)化決策和加工調(diào)度優(yōu)化決策以實(shí)現(xiàn)凈收益最大化是企業(yè)面臨的重要問題。在實(shí)際中，訂單接受決策和加工調(diào)度決策通常分別隸屬于銷售和生產(chǎn)兩個(gè)不同部門:銷售部門期望接受盡可能多的訂單以最大化銷售收入，而生產(chǎn)部門追求有效利用加工資源以提高企業(yè)生產(chǎn)力。盡管兩個(gè)部門可能進(jìn)行溝通與協(xié)調(diào)，但是由于它們之間的利益沖突以及缺乏有效的優(yōu)化理論和技術(shù)方法支持，可能導(dǎo)致訂單延期交付、

2、凈收益減少甚至客戶流失，難以實(shí)現(xiàn)企業(yè)的全局優(yōu)化目標(biāo)。因此，研究單件訂單接受與加工調(diào)度問題，同時(shí)確定需要接受的單件訂單并優(yōu)化其加工排序以最大化企業(yè)凈收益，具有重要的理論意義和應(yīng)用價(jià)值。
　　本文針對企業(yè)的實(shí)際運(yùn)作管理需求，首次構(gòu)建了納入考慮單件訂單分類、兩階段流水車間加工以及轉(zhuǎn)包加工策略等決策場景的若干單件訂單接受與加工調(diào)度問題優(yōu)化決策模型。上述問題的優(yōu)化決策模型約束繁多，結(jié)構(gòu)復(fù)雜，從復(fù)雜度理論上講是NP-hard的。因此，針對各個(gè)

3、問題模型分別設(shè)計(jì)簡單高效的優(yōu)化方法進(jìn)行求解也是本文的研究重點(diǎn)。具體而言，本論文的主要研究內(nèi)容包括:
　　(1)針對帶強(qiáng)制交貨期的單機(jī)分類訂單接受與加工調(diào)度問題，本文設(shè)計(jì)了一個(gè)改進(jìn)人工蜂群算法實(shí)現(xiàn)優(yōu)化決策。首先，考慮到單件訂單分類的特點(diǎn)，我們引入了訂單組的概念設(shè)計(jì)人工蜂群算法的鄰域操作;同時(shí)通過一系列改進(jìn)策略有效地提高算法的計(jì)算性能。包括采用兩個(gè)啟發(fā)式算法生成質(zhì)量優(yōu)異的蜜源個(gè)體;通過自適應(yīng)選擇策略進(jìn)行鄰域搜索;嵌入局部搜索算法以平衡

4、算法的全局探索和局部搜索能力;改變跟隨蜂階段的摒棄機(jī)制，保留適應(yīng)度較好的蜜源個(gè)體。最后，大量的仿真實(shí)驗(yàn)結(jié)果表明改進(jìn)人工蜂群算法能夠有效地求解大規(guī)模問題實(shí)例。
　　(2)針對可滯后完工的單機(jī)分類訂單接受與加工調(diào)度問題，本文提出了一個(gè)拉格朗日松弛啟發(fā)式算法。我們采用松弛訂單約束策略構(gòu)建拉格朗日松弛問題，通過嵌入相鄰訂單相異性約束提高松弛上界質(zhì)量。采用動(dòng)態(tài)規(guī)劃求解該松弛問題，并應(yīng)用次梯度算法更新拉格朗日乘子。然后，基于松弛解的啟發(fā)式信息

5、，結(jié)合研究問題的優(yōu)化性質(zhì)設(shè)計(jì)啟發(fā)式算法構(gòu)造可行解。本文通過隨機(jī)生成大量問題實(shí)例進(jìn)行一系列的仿真實(shí)驗(yàn)，結(jié)果表明所設(shè)計(jì)的拉格朗日啟發(fā)式算法能夠在合理時(shí)間內(nèi)求得大規(guī)模問題實(shí)例令人滿意的近優(yōu)解。
　　(3)針對兩階段流水車間單件訂單接受與加工調(diào)度問題，本文提出了一個(gè)基于深度優(yōu)先搜索分支策略的分支定界算法。相比于廣度優(yōu)先搜索，深度優(yōu)先搜索可以令算法較快地獲得一個(gè)問題可行解?；趦呻A段流水車間的結(jié)構(gòu)特征，分別設(shè)計(jì)了有效的啟發(fā)式算法和松弛算法以

6、求解問題下界和上界。通過求得的下界與上界，同時(shí)結(jié)合優(yōu)勢規(guī)則進(jìn)行算法剪枝。仿真實(shí)驗(yàn)結(jié)果表明，本文所設(shè)計(jì)的分支定界算法能夠在合理時(shí)間內(nèi)求解訂單規(guī)模等于20的問題實(shí)例最優(yōu)解。
　　(4)針對考慮轉(zhuǎn)包決策的單件訂單接受與加工調(diào)度問題，本文設(shè)計(jì)了一個(gè)候鳥優(yōu)化算法進(jìn)行求解。該算法采用兩個(gè)分別基于啟發(fā)式規(guī)則和拉格朗日松弛的啟發(fā)式算法生成候鳥個(gè)體，以保證初始種群的質(zhì)量;應(yīng)用迭代貪心算法的毀壞和構(gòu)造操作進(jìn)行鄰域搜索;通過引入局部搜索策略，平衡算法的