Parallelizing test, diagnose and fix tasks using graph partitioning algorithms

I.S.M. Jong, de, R. Boumen, J.M. Mortel - Fronczak, van de, J.E. Rooda

    Research output: Book/ReportReportAcademic

    54 Downloads (Pure)


    The development of a new semi-conductor manufacturing system, like the ASML waferscanner, is mainly driven by time-to-market. The final test phases during the development phase of a waferscanner can consist of many (100+) test cases. The duration of these test phases can be reduced by using an additional test system of the same configuration and execute the test cases in parallel. The set of test cases to be executed needs to be divided into two sets of test cases with equal test durations. And, the combined duration of the parallel test phases should be minimal. Several approaches exist to divide test cases into two sets of test cases. The standard bin-packing approach does not take into account that certain test cases are `overlapping' with each other, while this overlap could influence the total test duration in a positive and negative manner. In this paper, an algorithm is presented which partitions a set of test cases into two smaller sets of test cases, such that the minimal total test duration is obtained when these test sets are executed in parallel. The algorithm is based on a well known graph partitioning algorithm, which is adopted such that test cases (test graphs) can be partitioned. The algorithm uses an intuitive system test model as input and takes the effect of overlapping test cases, test stop criteria, the test sequence and the test process into account. The case on the ASML system shows that the duration of a test phase is reduced by 30% by parallezing a test phase.
    Original languageEnglish
    Place of PublicationEindhoven
    PublisherTechnische Universiteit Eindhoven
    Number of pages24
    Publication statusPublished - 2007

    Publication series

    NameSE report
    ISSN (Print)1872-1567


    Dive into the research topics of 'Parallelizing test, diagnose and fix tasks using graph partitioning algorithms'. Together they form a unique fingerprint.

    Cite this