供應(yīng)鏈調(diào)度中的生產(chǎn)計劃與分批策略研究.pdf

1、生產(chǎn)調(diào)度問題是一類經(jīng)典的組合最優(yōu)化問題，研究如何合理分配和調(diào)度有限資源以獲得最大效益，在實際的生產(chǎn)中具有廣泛的應(yīng)用。高效的調(diào)度方案可以提高生產(chǎn)設(shè)備利用率、降低成本，增加企業(yè)的利潤。供應(yīng)鏈調(diào)度問題是生產(chǎn)調(diào)度問題的擴展，研究的是供應(yīng)鏈的成員們（包括供應(yīng)商、制造商、分銷商和第三方物流等）在信息共享的基礎(chǔ)上，為了達到縮短產(chǎn)品交貨期，降低整條供應(yīng)鏈運作成本的目標(biāo)，實行聯(lián)合（或協(xié)同）的調(diào)度，對生產(chǎn)制造領(lǐng)域有著重要的研究價值。
　　首先，本文對

2、供應(yīng)鏈調(diào)度問題的研究背景和意義進行了歸納總結(jié)并對其國內(nèi)外研究現(xiàn)狀做了詳細(xì)介紹。
　　其次，對組合優(yōu)化問題、調(diào)度問題、相關(guān)算法及計算復(fù)雜性進行了回顧，同時對于調(diào)度問題的求解思路以及本文所采用的主要算法做了簡單介紹。
　　然后，研究了帶有分批配送的供應(yīng)鏈調(diào)度問題。我們先對原始問題作了復(fù)雜性分析，證明了該問題是強NP-hard問題;對于配送批次有常數(shù)上界的情形，我們證明了是一般的NP-hard問題，并設(shè)計了完全多項式時間近似方案(

3、FPTAS)。另外，我們還研究了三個多項式可解的子問題，對每個子問題設(shè)計了相應(yīng)的多項式時間最優(yōu)算法，并通過計算實例，驗證了算法的有效性。
　　接著，研究了具有惡化效應(yīng)的供應(yīng)鏈調(diào)度問題。同樣地，我們先對原始問題作了復(fù)雜性分析，證明了該問題是強NP-hard問題，并進一步證明了該問題不存在常數(shù)最壞情況界的多項式時間算法，除非P=NP;對于到達批次有常數(shù)上界的情形，我們對其做了復(fù)雜性分析，證明了該問題仍然是強NP-hard問題，并設(shè)計了