Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38611
Title: | 以反向拍賣法作代工廠間工作排程之研究 Reverse Auction-Based Job Scheduling among Contract Manufacturers |
Authors: | Ming-Ming Hsieh 謝旻旻 |
Advisor: | 張時中(Shi-Chung Chang) |
Keyword: | 委外,排程,拍賣,合約製造商,拉式解限, outsource,scheduling,auction,contract manufacturer,Largrangian relaxation, |
Publication Year : | 2005 |
Degree: | 碩士 |
Abstract: | 隨著交易市場全球化以及競爭日趨激烈的影響,有愈來愈多的製造業者仰賴外在的供應商提供原料或是零組件,以便專注於核心能力的發展。委外服務(outsourcing)在急欲提昇競爭力的資訊科技產業因而成為一項日益蓬勃的趨勢。
在這篇研究中,我們著眼於合約製造商之間工作排程的問題。多數的情況下,排程的方法大多發展在以資訊集中處理的前提下,或是資訊分散,但有共同合作的行為目標。然而,集中式的問題處理方法並不適用於問題中各個個體有自己獨立的目標,以及關於需求與價值衡量的私有資訊的情況。 我們比較多種拍賣法,最後選擇以反向拍賣法的概念來發展我們處理這項問題的演算法。工作的提供者只需要知道各項工作的價格,開始開工的時間以及預定的交期。拍賣的方法是以反覆多個回合的方式進行。 由於這個拍賣有非合作的性質,因此我們將分別模擬拍賣主持者與參與競標者的行為以及他們之間的互動關係。我們將拍賣主持者的問題規劃成一個簡單的貪心(greedy)分派問題。對他而言,他只需要考量分派工作所能得到的預期獲利以及未分派工作所受到的損失。而關於未完成或延遲完成的工作賠償則完全由工作得標者負擔。競標者內部的工作排程問題則是一個複雜度為NP-hard的問題。我們應用拉式解限(Lagrangian Relaxation)來分解這個問題。我們將經由數個實驗重新驗證他的功效。 此外,為了能夠使更貼近並應用於現實的情況,我們將會考慮到因有不確定因素,造成產品週期時間(cycle time)為一隨機變數(random variable)的情況。我們模擬隨機的週期時間,得到平均值以及變異數。經由重新規劃我們原來的數學模型,可以使原來的演算法更適用於實際情況。實驗結果顯示考慮到隨機週期時間的規劃演算法,在實際情況中週期時間隨機無法確定的時候,的確能得到比原來的演算法更好的結果。 由於在這個拍賣裡有許多獨立的決策者,理想解(optimal solution)的觀念在此將不適用。我們取而代之的以均衡解(equilibrium solution)的觀念來衡量結果。我們定義均衡解的意義為,在獲知其他人策略的情況下,決策者仍然無法改變決定以得到對自己更好的結果。接著我們證明經由我們的演算法得到的結果,將會在有限次數內收斂至一個均衡解。我們同時觀察了當競標者或是工作數量增加時,所需的回合亦會增加。並且競標者若不考慮隨機變數的情況將會使主持拍賣者獲利較多。 Pressed by market globalization and concomitant competition, more and more manufacturers are relying on their suppliers to provide raw materials and component parts so as to focus on their core competence. Outsourcing becomes an increasing trend due to the competitiveness of the IT (Information Technology) industry. In this study, we focus on the job scheduling problem among contract manufacturers. In almost all cases, however, scheduling methods are developed under the assumption of centrally available information, or distributed information with cooperative behavior. Nevertheless, centralized methods are not directly applicable in the problem where each entity has its own individual objective and privately held information about the requirements for and values of possible uses. We choose reverse auction among several kinds of auctions to develop our algorithm in solving the problem. Implementing the reverse auction mechanism, the job provider only has to know the price and the beginning time/delivering time of each job. The auction is processed through iterations. The auction is a non-cooperative game so we model auctioneer’s and bidder’s problems separately and consider their interactions. We formulate the auctioneer behavior and the assignment is a simple greedy assignment problem. For auctioneer, it only considers the expected profit from job assigned and the cost from job unassigned. The not or late delivering job compensation is all compensated by bidder. The scheduling problem of the bidder is a NP hard scheduling problem itself. We apply the Lagrangian Relaxation to decompose the problem. Several experiments are made to prove its efficiency. Besides, in order to be applied in the real condition, we will consider a situation where there are uncertainties and the cycle time of each job is a random variable. We simulate the stochastic cycle time and get its mean and variance. By re-formulating our mathematic formulation, we can make the algorithm be closer to the real problem. Experiment results show that the stochastic problem formulation perform better than the deterministic problem formulation when the cycle time is a random variable. Because there are several independent decision makers in the auction, the concept of an optimal solution is not suitable to use. We then use the concept of an equilibrium solution to evaluate the result. We define our equilibrium solution as that no entity can benefit from changing its strategy given the other entities’ strategies. We show that the auction will converge to an equilibrium solution in finite iterations. We also observe that iterations will increases while the number of bidders or jobs increases and the auctioneer will benefit if bidders use deterministic algorithm instead of deterministic algorithm. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/38611 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 電機工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-94-1.pdf Restricted Access | 941.88 kB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.