隨著整合度和複雜度持續的增加，IC產品測試需要有一個可靠的經濟解決方案。以測試項次數量與成品規模量的加成效果而言，每降低特定測試時間就能有極大的成本節省效益。本論文研究半導體產品測試時間縮短(Test Time Reduction, TTR)的方法，目標是找出最小化各測試流程的最大工作時間(Makespan)。在實現生產計畫之前，將產品測試項與輸入輸出匯流排預先規劃與評估。本研究比較不同解法的績效與品質，其中運用整數線性規劃法(Integer Linear Programming, ILP)及軟體工具(CPLEX)為輔，求得最佳化問題解作為參照。並於基因演算法(GA)求得問題解之後，運用田口式實驗計畫直交表(Orthogonal Array, OA)，施行實驗計畫法(DOE)評估演算法參數組合。實驗結果顯示以GA求得的解品質趨近甚至相同於CPLEX所得到的最佳解，特別在求解複雜問題時所花的時間方面GA相對CPLEX更有效率的多。

The sound economic solution is necessary for IC product testing with its increased integration and complexity. The cost saving is significant after test time reduction (TTR) whenever it implements on high product volume. The scheduling simulation evaluates test items and bus resources for preparing before manufacture. The goal of this study is for the test scheduling to minimize the makespan. We used CPLEX, a tool for ILP, to find optimal solutions for the problems. Meanwhile, we proposed a genetic algorithm (GA) to obtain approximate solutions, which is more time-efficient than CPLEX when the big problem sets. Taguchi method design of experiment (DOE) was used to evaluate the performance of parameter combination of GA for scheduling as well.

[1] Rajesh Kumar Arora, Vikram Sarabhai, Trivandrum, Arora, Rajesh Kumar, Optimization : algorithms and applications. CRC Press, pp139-166, 2015
[2] Peter Brucker. Scheduling Algorithms, Fifth Edition, Springer Printed book, 2006.
[3] Krishnendu Chakrabarty,"Design of System-on-a-Chip Test Access Architectures using Integer Linear Programming." IEEE 18th VLSI Test Symposium, pp.127-134, May 2000.
[4] Krishnendu Chakrabarty,"Test Scheduling for Core-Based Systems Using Mixed-Integer Linear Programming." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.19, no.10, pp.1163-1174, Oct. 2000.
[5] Richard M. Chou, Kewal K. Saluja and Vishwani D. Agrawal."Scheduling Tests for VLSI Systems Under Power Constraints.", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 5, no. 2, pp.175-185, June 1997.
[6] Rainer Dorsch, Ramdn Huerta Rivera, Hans-Joachim Wunderlich and Martin Fischer."Adapting an SOC to ATE Concurrent Test Capabilities." ITC International Test Conference, pp.1169-1175, 2002.
[7] Robert Fourer, David M. Gay and Brian W. Kernighan, AMPL A Modeling Language for Mathematical Programming. Second Edition, 2003.
[8] Vadim Geurkov and Lev Kirischian,"A Concurrent Testing Technique for Analog-to-Digital Converters." IEEE 17th International Mixed-Signals, Sensors and Systems Test Workshop, pp.133-136, 2011.
[9] Haidar M. Harmanani and Hassan A. Salamy,"Power-Constrained System-on-a-Chip Test Scheduling Using a Genetic Algorithm." The 3rd International IEEE-NEWCAS Conference, pp.203-206, June 2005.
[10] Yu Huang, Wu-Tung Cheng, Chien-Chung Tsai, Nilanjan Mukherjee, Omer Samman, Yahya Zaidan and Sudhakar M. Reddy,"Resource Allocation and Test Scheduling for Concurrent Test of Core-Based SOC Design." IEEE Test Symposium, Proceedings. 10th Asian, pp.265-270, Nov. 2001.
[11] Vikram Iyengar and Krishnendu Chakrabarty,"System-on-a-Chip Test Scheduling With Precedence Relationships, Preemption, and Power Constraints." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.21, no.9, pp.1088-1094, Sep 2002.
[12] Zhan Jinyu, Li Xunsheng, Guo Bing, Xiong Guangze and Sang Nan,"A Test Scheduling Scheme for Core-Based SoCs Using Genetic Algorithm." Embedded Software and Systems Symposia, ICESS Symposia, International Conference, pp.38-43, July 2008.
[13] Xrysovalantis Kavousianos, Krishnendu Chakrabarty, Arvind Jain and Rubin Parekhji,"Test Schedule Optimization for Multicore SoCs: Handling Dynamic Voltage Scaling and Multiple Voltage Islands", IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 31, no. 11, pp.1754-1766, November 2012.
[14] Xrysovalantis Kavousianos, Krishnendu Chakrabarty, Arvind Jain and Rubin Parekhji,"Time-Division Multiplexing for Testing SoCs with DVS and Multiple Voltage Islands." IEEE 17th European Test Symposium, pp.1-6, May 2012.
[15] Sandeep Koranne,"On Test Scheduling for Core-Based SOCs" Design Automation Conference, 15th International Conference on VLSI Design, pp.505-510, Jan 2002.
[16] Wen-Yang Ku, J. Christopher Beck,"Mixed Integer Programming Models for Job Shop Scheduling: A Computational Analysis." Computers and Operations Research, vol.73, pp.165-173, September 2016.
[17] Roy H. Kwon, Introduction to Linear Optimization and Extensions with MATLAB. CRC Press, pp.1-36, 2014.
[18] Erik Larsson, Klas Arvidsson, Hideo Fujiwara and Zebo Peng."Efficient Test Solutions for Core-Based Designs." IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 23, no. 5, pp.758-775, May 2004.
[19] Timothy Lyons, George Conner, John Aslanian and Shawn Sullivan,"The Implementation and Application of a Protocol Aware Architecture." IEEE International Test Conference, pp.1-10, Sept. 2013.
[20] Lars Monch, JohnW Fowler, Stephane Dauzere-Peres, Scott J. Mason and Oliver Rose,"A survey of problems, solution techniques, and future challenges in scheduling semiconductor manufacturing operations." Journal of Scheduling, vol. 14, no.6, pp.583-599, December 2011.
[21] Takahiro Nakajima, Takeshi Yaguchi and Hajime Sugimura,"An ATE Architecture for Implementing Very High Efficiency Concurrent Testing." IEEE International Test Conference, pp.1-10, 2012.
[22] Jochen Rivoir,"Parallel Test Reduces Cost of Test More Effectively Than Just a Cheap Tester." Electronics Manufacturing Technology Symposium, IEEE/CPMT/SEMI 29th International, pp.263 - 272, July 2004.
[23] Soheil Samii, Mikko Selkala, Erik Larsson, Krishnendu Chakrabarty, and Zebo Peng,"Cycle-Accurate Test Power Modeling and Its Application to SoC Test Architecture Design and Scheduling." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.27, no.5, pp.973-977, May 2008.
[24] Jingbo Shao, Guangsheng Ma, Zhi Yang and Ruixue Zhang,"Process Algebra Based SoC Test Scheduling for Test Time Minimization." IEEE Computer Society Annual Symposium on VLSI, pp.134-138, April 2008.
[25] Makoto Sugiharay, Hiroshi Datez and Hiroto Yasuuray,"Analysis and Minimization of Test Time in a Combined BIST and External Test Approach." IEEE Design, Automation and Test in Europe Conference and Exhibition, pp.134-140, Mar 2000.
[26] S. Sumathi, T. Hamsapriya, P. SurekhaEvolutionary, Evolutionary Intelligence: An Introduction to Theory and Applications with Matlab. Springer Printed book, pp31-75, 2008.
[27] Yasuhiro Takahashi and Akinori Maeda,"Multi Domain Test: Novel Test Strategy to reduce the Cost of Test." IEEE 29th VLSI Test Symposium, pp.303-308, May 2011.
[28] Yasuhiro Takahashi, Akinori Maeda and Mitsuhiro Ogura,"Actual Implementation of Multi Domain Test: Further Reduction of Cost of Test." International Test Conference, pp.1-8, Sept. 2011.
[29] Fotis Vartziotis, Xrysovalantis Kavousianos, Krishnendu Chakrabarty, Arvind Jain and Rubin Parekhji,"Time-Division Multiplexing for Testing DVFS-Based SoCs." IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 34, no. 4, pp.668-681, April 2015.
[30] Bethany Van Wagenen and Edward Seng,"Concurrent Test Planning." IEEE International Test Conference, pp.1-10, Nov. 2010.
[31] Qiang Xu, Nicola Nicolici, and Krishnendu Chakrabarty,"Test Wrapper Design and Optimization Under Power Constraints for Embedded Cores With Multiple Clock Domains." IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol.26, no.8,pp. 1539-1547, Aug. 2007.
[32] Dan Zhao and Shambhu Upadhyaya,"Dynamically Partitioned Test Scheduling With Adaptive TAM Configuration for Power-Constrained SoC Testing." IEEE Transactions on Computer-aided Design of Integrated Circuits and Systems, vol. 24, no. 6, pp956-965, June 2005.
[33] Dan Zhao and Shambhu J. Upadhyaya,"A Generic Resource Distribution and Test Scheduling Scheme for Embedded Core-Based SoCs." IEEE Transactions on Instrumentation and Measurement, vol.53 no.2, pp318-329, April 2004.
[34] AMPL Streamlined Modeling For Real Optimization., (http://ampl.com/products/ide/)
[35] IBM ILOG CPLEX Optimization Studio User's Manual.
(http://www.ibm.com/support/knowledgecenter/SSSA5P_12.6.3/ilog.odms.studio.help/Optimization_Studio/topics/COS_home.html)