以反向拍賣法作代工廠間多步驟工作分派與排程之研究

Abstract

隨著交易市場全球化以及競爭日趨激烈的影響，有愈來愈多的製造業者仰賴外在的供應商提供原料或是零組件，以便專注於核心能力的發展。委外服務(outsourcing)在急欲提昇競爭力的資訊科技產業因而成為一項日益蓬勃的趨勢。 在本篇研究中，我們著眼於在半導體供應鏈中的委外服務,討論工作提供商與合約製造商之間工作分派與排程的問題。在整個半導體供應鏈中，無廠房的IC設計公司(fabless design houses of integrated circuits)產生各種工作的訂單並尋求適合的晶圓代工服務提供者(foundry service providers)。另一方面，晶圓代工廠間亦藉由提供低價且適時的代工服務以爭取訂單。在此既競爭又合作的環境下,各個決策者(decision-makers)，也就是工作提供商和代工廠，都保留各自私有的資訊，如:對工作的估價，各自的產能和操作限制等，故傳統集中式的問題處理方法並不適用在於這樣競合的環境。 為能使各決策者在保留各自私有資訊的情況下順利完成工作的分派，我們選擇以反向拍賣法的概念來發展我們處理這項問題的演算法。在拍賣的過程中，工作提供商只需公佈其工作的需求和完成工作可得的報償,而工作處理者在競標工作時，則只需提供對各工作的折扣和預期的交期。拍賣的方法是以反覆多個回合的方式進行。在每回合的拍賣中，每位工作處理者藉由提出相較於上回合更高的折扣去競標工作,而工作提供商將在每回合的拍賣中,暫時將各個工作分派給當回合提出最高折扣的工作處理者,拍賣將以此方式反覆多個回合進行直到沒有更高的折扣再提出,則當回合的結果即為最終工作分派的結果。 由於這個拍賣有非合作的性質，因此我們將分別對拍賣主持者與參與競標者的行為以及他們之間的互動關係建立數學模型。我們將拍賣主持者的問題規劃成一個整數規劃(integer-programming)的工作分派問題。對他而言，他只需要考量分派工作所能得到的預期獲利以及未分派工作所受到的損失。而關於未完成或延遲完成的工作賠償則完全由工作得標者負擔。 而對競標者(即工作處理者)而言,其問題是如何藉由競標合適的工作以期得到最大的獲利,故其必需藉由處理排程上的問題來決定該競標哪些工作，和計算完成工作可得的獲利和遲交或早交所造成的罰金。而在處理排程問題的過程中需考慮工作上的限制,如產能的限制(capacity constraint)和操作先後次序的限制(operation precedence constraint)等。我們應用拉式解限(Lagrangian Relaxation)來分解成為各別工作排程的問題,並使用次梯度法(sub-gradient method)調整拉氏算子(Lagrange multipliers)。此外，為了能夠使更貼近並應用於現實的情況，我們將會考慮到因有不確定因素，造成產品週期時間(cycle time)為一隨機變數(random variable)的情況。我們模擬隨機的週期時間，得到平均值以及變異數。一個以模擬為基礎的啟發式演算法將被將使用於解決此種含有考慮不確定因素的排程問題,經由重新規劃我們原來的數學模型，可以使原來的演算法更適用於實際情況。 實驗結果顯示考慮到隨機週期時間規劃的演算法，在實際情況中,週期時間隨機無法確定的時候，的確能得到比原來的演算法更好的結果，也就是若是僅以平均時間來做排程規劃的問題,則雖然使用的是一似近最佳化的排程方法，但其得到的結果卻比不上有考慮不確定因素但排程方法卻是較差的演算法。且當競標者考慮到不確定的因素時，對於拍賣主持者及參與競標者的拍賣結果，都有很大的影響。另外藉由模擬拍賣中含有不對稱能力的競標者的情況，對拍賣主持者而言，當工作處理者延遲工作時，拍賣主持者也該會有自己的損失，故在拍賣主持者分派工作時，也該將工作處理者延遲工作的機率納入考慮。

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 assignment and scheduling problem between job provider and contract manufacturers. In the semiconductor supply chain, fabless design houses of integrated circuits generate various job orders and compete for the capacity of qualified foundry service providers. On the other hand, foundry fabs/companies compete to get the job orders by providing low cost and timely manufacturing services. In this not only competed but also cooperative environment, all the decision-makers (DMs), i.e., job owners and fabs all hope keep their private information such as ones’ own valuation of jobs, actual capacity and operational constraints. So, traditional centralized methods are not directly applicable in the problem. In order to make DMs can assign jobs with keeping private information, we choose reverse auction among several kinds of auctions to develop our algorithm in solving the problem. A job order owner announces job requirements and payments for fabs to bid on while qualified fabs bid on a job by offering the discount to payment and processing schedule of the job. The auction is processed through iterations. In each round of bidding, the bidders send job “bids” to the auctioneer and the auctioneer then temporarily assigns each job to the bidder who offers the highest bid on the job. The highest bid on each job serves as the starting bid for the job in the next round of bidding. The auction repeats round by round till no new bids are offered and the final assignment is determined. 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 an integer-programming 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. For bidder, his problem is how to get the maximum profit by biding jobs. So, the objective of a fab is to maximize the payment it may receive from processing the jobs minus the earliness/tardiness penalty for each job not processed within the desired time window of the job and subject to local constraints such as capacity constraint and operation precedence constraint. We apply the Lagrangian Relaxation to decompose the problem into individual job scheduling problems, and updated Lagrange multipliers according to a sub-gradient method. 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. A simple heuristics with job schedule evaluation by simulation are adopted in the bidder’s scheduling algorithm. 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 performs better than the deterministic problem formulation when the cycle time is a random variable, i.e., the algorithm with consideration of uncertainties has a better performance than optimality of the mean value-based bidder scheduling algorithm. And the consideration of uncertainties in bidders’ decisions has a lot of impact on performance of both bidders and the auctioneer. Besides, we simulate the case where there are asymmetric logistic capability bidders in the auction and the experiment result that auctioneer should also has risk when a bidder winner delays the job delivery. So when auctioneer assign job, he should take the consideration of risk in his decision.