Semiconductor final test scheduling with Sarsa([lambda], k) algorithm

Zhicong Zhang, Li Zheng, Forest Hou and Na Li

European Journal of Operational Research, 2011, vol. 215, issue 2, 446-458

Abstract: Semiconductor test scheduling problem is a variation of reentrant unrelated parallel machine problems considering multiple resource constraints, intricate {product, tester, kit, enabler assembly} eligibility constraints, sequence-dependant setup times, etc. A multi-step reinforcement learning (RL) algorithm called Sarsa([lambda], k) is proposed and applied to deal with the scheduling problem with throughput related objective. Allowing enabler reconfiguration, the production capacity of the test facility is expanded and scheduling optimization is performed at the bottom level. Two forms of Sarsa([lambda], k), i.e. forward view Sarsa([lambda], k) and backward view Sarsa([lambda], k), are constructed and proved equivalent in off-line updating. The upper bound of the error of the action-value function in tabular Sarsa([lambda], k) is provided when solving deterministic problems. In order to apply Sarsa([lambda], k), the scheduling problem is transformed into an RL problem by representing states, constructing actions, the reward function and the function approximator. Sarsa([lambda], k) achieves smaller mean scheduling objective value than the Industrial Method (IM) by 68.59% and 76.89%, respectively for real industrial problems and randomly generated test problems. Computational experiments show that Sarsa([lambda], k) outperforms IM and any individual action constructed with the heuristics derived from the existing heuristics or scheduling rules.

Keywords: Scheduling; Semiconductor; Reinforcement; learning (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221711005005
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:215:y:2011:i:2:p:446-458

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().