列印此頁 列印此頁

學術發展1

先進自動化排程技術

文/傅立成(資訊/電機工程學系教授)

 

    「排程」泛指決定一連串事件發生的時間、地點或方式,更通俗的定義為決定事件發生的順序。一般而言,基本的排程能力可說是人類與生俱來的能力之一,一個有行為能力的人在每日的生活作息中經常要決定事件處理的先後次序,決定的準則不外乎是為求達最大的效益、解決最多的工作量,或避免超過時限,因此一位被稱為有效率的人,常是排程能力強的人。

    不過,在人類的日常生活作息中,需排程決定處理先後次序的事件數一般不大,因此能力強的人常可在極短的時間之內,以類似直覺式的方式,即可達到幾乎是最佳的排程效果;類似的方式亦常被應用到規模不大或複雜度不高的生產工業中,常見的現象即是線上領班根據其經驗或利用直覺方式來決定產品加工或生產的次序。但是,隨著應用領域的不同,待排程的事件數可能過多或事件彼此間又存在複雜的前後牽制關係,是以問題的困難度及複雜度可能早已超過人類以直觀的方式即可解決的範圍,而且排程效果的好壞可能事涉重大的利害關係,此時,電腦超強的計算能力即成為排程的利器。

    雖然電腦對數字處理能力遠遠超乎人類同性質的能力之上,但如何將一般排程問題轉化為電腦可有效處理的問題即為一門重要的學問,稱為「自動化排程」,相關的技術包括如何(一)在電腦中建立應用問題的模型,(二)根據排程的優窳標準訂定成本或代價函數,(三)設計一智慧、有效率的計算流程,(四)分析計算結果的最佳化程度。以下茲舉兩例以做說明:

例一:半導體廠的排程

    半導體廠為當前高科技產業中最複雜的生產工廠之一,全廠造價金額高達數百億元,內含設備機台多達數百台,以晶元代工廠而言,每樣產品製程可牽涉數百道步驟,而全廠的運轉滿載時,在製品的數量可達數千卡匣(一卡匣可含24片晶元),換言之,工廠的生產須滿足多達數十件客戶訂單的交貨期,由於在製品的附加價值高,延遲交貨的罰則嚴峻,則排程結果的好壞對廠商的獲利具重大的影響,是以,半導體廠的自動化生產排程問題即顯得困難但重要。鑒此,本研究團隊,近來提出一套排程方案[1]-[4],可有效解決複雜晶元代工廠的排程問題,更衍生出交期預測的解決對策。詳言之,該方案(一)利用新提出的「排隊裴氏網路」(Queueing Petri Net)技術供問題有效建模,(圖一);(二)利用基因(chromosome)編碼及最適函數(fitness function)作為成本函數及評估的對象;(三)利用遺傳基因演算法來作為計算流程(圖二);(四)分析出排程結果隨計算時間的漸近優越性。

例二:高樓電梯群控

    隨著高樓的迅速增加,良好的垂直交通運輸,在現代化大樓的評估中,逐漸成為不可忽視的要素。電梯設備是大樓內最主要的運輸工具(圖三),而電梯群控系統則主宰了電梯設備的效能。電梯群控系統的主要目的,在於協調多部電梯運載的次序及方式,以期有效率地完成乘客的運輸需求,為一典型動態排程的問題。為發展一個優秀的電梯群控系統,本研究群針對群控系統的三個主要層面 - 模型建構、排程演算法及系統適應能力作了完整的考慮與設計(圖四)[5]-[6]。適當的系統模型有助於問題的描述與演算法的設計,系統模型能否表現實際面臨的問題,對於群控系統的實用性也有很大影響。面對由乘客、服務需求與電梯設備所組成的動態事件系統,裴氏網路(Petri nets)是一個很適合的建模方法。該建構之模型同時考慮了電梯的加減速動態,以求更精準地表現真實的電梯系統。在此模型上,我們發展了一套以模擬器為主軸的排程演算法,用來控制電梯設備,快速完成乘客的服務需求。此演算法不但考慮了乘客的等待時間、搭乘時間、電力消耗等三項主要評估要素,另外還有重新排程的機制,能夠動態改變電梯與服務需求的指派關係,更增進電梯系統的效能。另外,類神經網路的引入,使我們能夠掌握未來服務需求的時間與頻率,在服務需求尚未發生前,事先調度電梯設備,提供乘客更快捷的服務。最後,在系統適應能力方面,以我們所使用的模組化建構方式,不管建築物的樓層數、電梯數有多少,我們都能很快地完成電梯系統的模型,並在其上應用我們的群控系統;類神經網路的子系統,也能在各個不同性質的建築中,協助群控系統分析建築物的交通流程與交通模式,讓群控系統作出最適切的排程策略。

參考文獻

[1]  Sun, T.-H., C.-W. Cheng, and L.-C. Fu, “Petri-Net Based Modeling and Scheduling for Flexible Manufacturing System,” IEEE Transactions on Industrial Electronics, (SCI) Vol. 41, No.6, pp. 593-601, 1994.

[2]  Lin, M.-H. and L.-C. Fu, “Modeling, Simulation, and Performance Evaluation of an IC Wafer Fabrication System,” International Journal of Production Research, Vol.38, No.14, pp.3305-3342, (SCI) 2000.

[3]  Chen, J.-H., L.-C. Fu, M.-H. Lin and A.-C. Huang, “Petri-Net GA Based Approach to Modeling, Scheduling, and Performance Evaluation for Wafer Fabrication,” Conditionally Accepted, IEEE Transactions on Robotics and Automation, (SCI) 2000.

[4]  Lin, Ming-Hung “Modeling, Analysis, Prediction and Scheduling forVisual Wafer Fabs”, 台大資訊工程系博士論文, 2001

[5]  Huang, Y.-H. and L.-C. Fu, “Dynamic Scheduling of Elevator Systems over Hybrid Petri Net/Rule Modeling,” Proc. IEEE International Conference on Robotics and Automation, pp. 1805-1810, 1998.

6] Ho, Y.-W. and L.-C. Fu, “Dynamic Scheduling Approach to Group Control of Elevator Systems with Learning Ability,” Proc. IEEE International Conference on Robotics and Automation, San Francisco, 2000.

發表迴響

你可以使用 HTML標簽

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>