考量交期因素下最佳測試方法選擇之研究

Optimal Inspection Method Selection with Due Date Consideration

呂瑩(Ying Leu)

指導教授 ： 蔣明晃

共同指導教授 ： 郭瑞祥(Ruey-Shan Guo)

國立臺灣大學/管理學院/商學研究所/碩士(2011年)

https://doi.org/10.6342/NTU.2011.01108

摘要

過去大部分單機台排程問題，主要以工作任務處理時間確定下為前提，無論是製造或測試皆是如此，若要加入變化，則是進一步討論處理時間為某一範圍內的特定分布亦或是近年來討論熱烈的學習與退化效果，但這些處理時間或處理方法是無法事前選擇的。

本研究所探討的問題發生於品牌銷售商的測試部門，測試部門必須負責上市前的產品前測，以確定產品是否沒有問題。測試部門本身有多種測試法可以選擇，越精確的測試所花的時間越長，考量測試完成時間與測試正確性，測試部門必須做出取捨，找出最適合的測試方法與測試順序。此問題為處理時間與處理方法可選擇之單機排程問題，由於處理時間可以選擇，因此能夠變化的可能性更大，不同的處理時間組合則會影響排序的最適結果，無法以單純的單機排程演算法處理。在此情況下，本研究將問題切成兩部分來看，一是測試方法的選擇，二是處理方法選定後的最佳排序。測試方法部分以基因演算法選出，並將此選擇的結果以分枝界限法的方式由後向前排序，找出最低目標成本之最佳排序方式與算出對應的成本作為基因演算法的適應度函數值參考依據，最後再將這些測試組合進行多次演進，找出最佳的解決方案。

關鍵字

測試方法選擇 ； 基因演算法 ； 交期限制

並列摘要

Job processing time is defined in most single machine scheduling problem, no matter in inspection or manufacturing side. If want to make some differences, usually would let the time be in certain distribution or concern the learning and deteriorating effect with job sequence. But these jobs’ processing time can’t be selected in the beginning.
In this thesis, the problem is happened in the test department of product brand owner’s company. The test department needs to do the inspections and make sure product doesn’t have any problems before product released to market. The department has many different kinds of inspection methods. The longer the inspection time is, the more accurate the inspection is. The department needs to make a trade-off between inspection methods and job priorities. It’s a kind of single machine scheduling problem, because the inspection method can be selected, it’s more complicated than normal scheduling problem. Different inspection method combinations would affect the optimal solution’s result. In this situation, we separate this problem into two parts. First, we select the inspection method combination. Second, we use this combination to find out the optimal test sequence. We use genetic algorithm to select the inspection combination and use branch and bound’s concept to find the optimal test sequence and calculate the cost which would be the reference of fitness in genetic algorithm. Then we take these combinations to evolve into many generations and we can find the optimal solution after evolution.

並列關鍵字

Inspection method selection ； Genetic algorithm ； Due day consideration

參考文獻

3.蔡杭助，結合基因演算法與離散事件模擬求解即時性平行機台之派工規劃問題，國立成功大學製造工程研究所碩士論文，2002。

2.Browne, S., & Yechiali, U. (1990). Scheduling deteriorating jobs on a single processor. European Journal of Operational Research, 38, 495-498.

3.Carlier, J., & Pinson, E. ( 1989 ). An algorithm for solving the job shop problem. Management Science, 35, 164-176.

4.Chao, X., & Pinedo, M. ( 1999 ). Operations Scheduling with Applications in Manufacturing and Services. Irwin McGRAW-Hill, U.S.A..

5.Chen, J., & Askin, R. G. ( 2007 ). Project selection, scheduling and resource allocation with time dependent returns. European Journal of Operational Research, 193, 23-34.