An efficient memetic algorithm for the graph partitioning problem

We consider the component testing problem of a device that is designed to perform a mission consisting of a random sequence of phases with random durations. Testing is done at the component level to attain desired levels of mission reliability at minimum cost. The components fail exponentially where the failure rate depends on the phase of the mission. The reliability structure of the device involves a series connection of nonidentical components with different failure characteristics. The optimal component testing problem is formulated as a semi-infinite linear program. We present an algorithmic procedure to compute optimal test times based on the column generation technique, and illustrate it with numerical examples.