搜索
第六十二期（民國九十七年九月）：69-96.物流中心供應商進貨配送排程問題求解模式與方法之實證研究林益州*蘇雄義**（收稿日期：96年7月12日；第一次修正：96年11月1日；接受刊登日期：97年5月20日）摘要本文旨在探討個案物流公司物流中心供應商進貨配送排程問題之模式特性與求解方法，以供個案公司實務應用之需。透過建構個案公司物流中心供應商進貨配送排程最佳化整數規劃模式(ISSD-IP)，採用最佳化演算法及啟發式演算法進行演算分析，探討符合供應商配送需求及物流中心作業限制的最佳月台數量、供應商月台分派、及配送排程表。經分析發現ISSD-IP為作業研究中典型的一維裝箱條碼問題(onedimensionalbinpackingproblem)，本文採取歷年研究結果表現較佳之啟發演算法FFD及BFD，以之作為求解方法，並將運算結果與最佳化求解結果及運算時間比較分析，BFD可以得到最快速及最佳的啟發解。實證研究取用個案物流公司北部常溫物流中心2006實際供應商配送資料，進行分析模式建構與分析，分析結果顯示個案公司在物流中心規劃資源、月台數目、供應商等候時間等相關資源之最佳使用將可產生三百一十萬元的節省效果，並可大幅增進與供應商之進貨排程協作效益。分析模式啟發演算法的敏感度分析*醒吾技術學院國際貿易學系講師。**東吳大學企業管理學系教授兼供應鏈與物流管理研究室召集人。第六十二期結果顯示求解品質BFD均優於FFD，但是運算速度則BFD略遜於FFD，但是運算速度均在個案企業可以接受的範圍內。關鍵詞：供應商進貨配送排程、最佳化、啟發求解、裝箱問題、月台壹、緒論一、研究動機隨著工商業之發達，支撐連鎖零售業有效發展的物流配送業已成為現代物流的主要象徵。然而，白熱化的競爭環境，促使物流配送業者間激烈之價格競爭，造成利潤愈趨微薄的現象。加上九十四年七月勞退新制實施後，物流配送業人力資源成本更加提高，使得營運環境愈形艱困，迫使業者紛紛採取委外、時薪、計件等人資策略，以因應高成本增加的壓力。為維持甚至增加利潤水準，各家業者乃競相尋求自有資源利用率最佳化的各種途徑，以提升資源運用之生產力與報酬率。物流中心為物流配送業的主要營運設施，一年營運時間幾乎全年無休，而且每日進貨供應商家數不僅多，而且貨量也非常大。在繁忙時期，進貨月台經常非常壅塞，造成月台不足、人力與搬運機具調派不當、廠商延誤交貨、冗長等候時間、以及影響出貨月台作業等等服務品質及成本增加的問題，對物流配送業及其供應商帶來非常大的有形及無形成本。因此，如何依據每日進貨廠商家數與進貨數量進行最佳之供應商進貨配送排程(inboundschedulingofsupplierdelivery，ISSD)，進而規劃適當的月台數量、理貨作業人力並有效指派供應商卸貨月台，乃成為物流配送業提高資源利用率、降低作業成本，甚至改善與供應商關係的一個重要物流規劃課題。本研究旨在探討個案物流公司供應商進貨配送排程最佳化之相關問題，透過建構供應商進貨配送排程最佳化整數規劃模式(ISSD-IP)及進一步的啟發式演算法求解分析，探討供應商配送排程表、供應商進貨月台分派、及進貨月台數量的改善方案。經分析發現ISSD-IP為作業研究典型一維裝箱條碼問題(onedimensionalbinpackingproblem)，本研究參考歷年研究結果表現較佳之啟發式演算法FFD及BFD進行求解，並與最佳化結果比較分析。研究物流中心供應商進貨配送排程問題求解模式與方法之實證研究蒐集個案公司北部常溫物流中心四月份一週的實際供應商進貨資料，進行ISSD-IP建模與求解分析，以檢測最佳化分析所得結果在實務應用上資源節省之效果及對供應商帶來的協作效益。研究並選取其他三季各一週的實際供應商進貨資料，以進行敏感度分析，期能了解不同需求的各週間的解答是否有很大的差異，藉以驗證啟發式演算法是否會因為樣本差異而有不同的表現。二、研究目的本研究乃在探討個案物流公司物流中心供應商進貨配送排程之改善，透過最佳化分析尋求降低進貨月台數量及合理化供應商進貨配送排程。研究重點說明於下：深入了解個案物流公司供應商進貨配送排程之作業現況。建構個案物流公司供應商進貨配送排程最佳化模式及求解方法，尋求供應商進貨配送排程之解答，包含最適月台數量、供應商月台分派及供應商進貨配送排程。貳、文獻探討本文供應商進貨排程問題的研究方法，最主要參考排程及裝箱問題的文獻，並從中選擇出合宜的分析方法。一、排程排程(scheduling)乃是將各項工件、訂單、製造、生產、設備、設施等資源作整體規劃，使資源能充分運用達到最佳使用的目的。排程研究在製造業生產規劃上應用非常廣泛，近年來也陸續有研究應用在港口裝卸貨櫃、醫院手術房、車輛派遣的規劃。在學術及產業領域的研究已有上百種排程方法被提出(Graves，1981)，定義排程是「在一段時間內，為達成設立工作的目標，有效分配可使用的資源來處理一群工件。」一個好的排程規劃系統可以提高企業資源的利用率、增加產出率。Baker(1984)提出平行機器排程問題，歸類有總時程最小化、總流程時間最小化及總延遲時間最小化，都是屬於NP-Hard的問題。平行機器依機第六十二期器、工件及加工時間的相同及不同又可區分為IdenticalParallelMachine、UniformParallelMachine、UnrelatedParallelMachine等三種(Allahverdi及Mittenthal，1994)。Hariri及Potts(1991)以啟發式演算法，探討不相關平行機器上求解最大完工時間最小化。Piersma及VanDijk(1996)以塔布搜尋法、模擬退火法，及基因演算法，求解總時程最小化。探討不相關平行機器上求解最大延遲石間最小化有GAP-EDD演算法（Suresh及Chaudhuri，1994）。求解總時程最小化有塔布搜尋法、模擬退火法，及基因演算法（Piersma及VanDijk，1996）。求解最大延遲時間最小化有以基因演算法與局部搜尋法之混合演算法(MemeticAlgorithms)(Cheng及Gen，1997)。探討相同平行機器，求解總延遲時間最小化有以基因演算法（Funda及Ulusoy，1999）。探討不相關平行機器上求解總加權延遲時間最小化有啟發式演算法與分枝界限法（林暘桂，民90）。另有研究以基因演算法（李勝隆，民92）探討不相關平行機器上求解總延遲時間最小化。傳統生產排程問題可依工件及作業特性區分為靜態排程(staticscheduling)與動態排程(dynamicscheduling)。靜態排程是工件數量及作業內容在加工前就已知且固定不變；動態排程是工件數量及作業內容在加工前及加工中會隨時間而變動。若工件的加工時間是固定，則稱為確定性(deterministic)的排程；加工時間不固定，為某種機率分配時，稱為隨機性(stochastic)的排程(林我聰，民83)。排程的品質衡量區分為最小成本及最佳績效。常用的成本衡量有固定成本、變動成本、存貨成本、延遲成本與缺貨成本。最佳績效有閒置時間最短、產出數量最大、彈性的中途插工單等二十七項排程績效評估(Mellor，1966)。排程問題的解決方法（葉財榮，民93）主要區分為兩種：數學規劃法及啟發演算法。數學規劃法求解需要較長時間求取最佳解，且隨機器或使用資源數量增多時，其求解時間以乘冪倍數遞增。分枝界限法(branchandbound)及動態規劃法(dynamicprogramming)為常見之最佳化求解方法。巨集啟發演算法(meta-heuristics)是針對不同問題特性發展出來的混合式啟發演算法，往往只能求得近似最佳解，但求解只需較短的時間，因此廣為運用在排程問題的研究。常見之啟發式演算法有深度搜尋法(depthfirstsearch)、廣度搜尋法(breadthfirstsearch)、塔布搜尋法(tabusearch)、模擬退火法(simulated物流中心供應商進貨配送排程問題求解模式與方法之實證研究annealing)、基因演算法(geneticalgorithm)、類神經網路法(neuralnetwork)等。二、裝箱問題近年關於裝箱問題求解方法的研究仍然集中在啟發演算法（Zhang、Cai、及Wong，2000）。有結合塔布搜尋法及分枝界限法（Scholl、Klein及Jurgens，1997）提出BISON(binpackingsolutionprocedure)演算法，求解效果佳，但演算複雜，求解時間長。MBS(minimun-bin-slack)演算法（Gupta及Ho，1999）求解效果比FFD及BFD佳，比BISON差，但求解時間較BISON短。Fleszar(FleszarandHindi，2002)提出修改自MBS的五種演算法，有MBS演算法、RelaxedMBS演算法、PerturbationMBS演算法、SamplingMBS演算法及VariableNeighborhoodSearch(VNS)MBS演算法，以避免區域最佳解，求解效果較MBS佳，但較BISON差。最近有與傳統求解目的相反，找出箱子使用數最大化，及可裝箱品項數最小化而提出MaximumResourceBinPackingProblem的研究（Boyar、Epstein、Fa-vrholdt、Kohrt、Larsen、PedersenandWohik，2005）。裝箱問題(binpackingproblem)為一種組合最佳化問題，可依品項數量、品項大小、箱子容量、及箱子數量的不同設定，區分為四種不同問題類型（邱柏憲，民91）。基本裝箱問題為「在品項數量、品項大小及箱子容量已知，且品項裝填不可超過箱子容量之限制下，求出可將所有品項裝完的最少箱子數目。」裝箱問題可以建構為一個(0,1)數學整數規劃模式，並採用最佳化方法求解，但實務上卻很少採用最佳化方法，因為求解時間往往隨問題增大而以乘冪倍數遞增。裝箱問題的啟發演算法早在1980年代初就被提出，主要有首配遞減法(first-fit-decreasing，FFD)及優配遞減法(best-fit-decreasing，BFD)兩種，以下簡述這兩種演算法之演算步驟。FFD（Gupta及Ho，1999）步驟1：將所有品項依大小由大至小排列。步驟2：從最大品項開始選取，一次放置一個品項到箱子中。步驟3：列出已使用的箱子，從剩餘空間容量大於被選取品項大小的箱子中，挑選出「剩餘空間最小」的箱子，將該品項放入選出的箱子中。第六十二期步驟4：若無符合步驟3的箱子，則再多加一個空箱子，將被選取的品項放入該空箱子中。步驟5：重複步驟2、3、4，直到所有的品項都被放入箱子中。步驟6：計算總共使用幾個箱子。BFD（Gupta及Ho，1999）將FFD演算法步驟3中「剩餘空間最小」，改為「剩餘空間最大」，其餘步驟皆相同。以上兩種演算法十分相似，僅步驟3不同，其運算速度都很快，求解效果經證明（Gupta及Ho，1999）解答值將介於(11/9)*nFFD(BFD)(11/9)*n+4之間，n是最佳解箱子數量。三、綜合討論本文在撰寫時查閱過知名國際期刊，如Interfaces,ManagementScience,EuropeanJournalofOperationalResearch等，均無找到關於物流中心進貨配送排程問題之相關研究論文，國內碩博士論文更是沒有任何先例可供參考。經分析排程文獻並無可以運用之處，但進貨碼頭開放時間與供應商進貨數量大小可比擬裝箱問題中箱子大小與品項大小，所以研究團隊乃採用裝箱問題來探討物流中心進貨配送排程問題。但因目前尚無一種多項式演算法能求出裝箱問題的最佳解，本研究採取文獻中表現較佳的FFD及BFD演算法進行較為深入的求解分析。參、建構物流中心供應商進貨配送排程問題最佳化模式與求解設計一、背景說明連鎖便利商店已成為台灣家喻戶曉的行業，而且也是多數人每日必經採購之處。目前主要連鎖便利商店包含統一超商(7-11)、全家、萊爾富、O