Feature-Extraction-Based Iterated Algorithms to Solve the Unrelated Parallel Machine Problem With Periodic Maintenance Activities

Abstract

This paper considers an unrelated parallel machine problem with job release times and maintenance activities, in which machines have to periodically undergo maintenance since the status of the machines will be deteriorated by job-induced dirt. The problem is inspired by a wet station for cleaning operations in a semiconductor manufacturing process. The objective is to minimize the makespan. Since the considered problem is proven to be NP-hard, obtaining optimal solutions is almost impossible in a reasonable computational time when the problem becomes large. We develop specific feature-extraction procedures to recognize important information in a job sequence and linkage encoding (LE) procedures to generate new job sequences. The two above procedures are embedded into an iterated algorithm, called a feature-extraction-based iterated algorithm (FEBIA), to obtain optimal or better solutions for the considered problem. To examine the performance of the FEBIA, the FEBIA is compared with two population-based algorithms, the particle swarm optimization (PSO) algorithm and the genetic algorithm (GA), using many test data. The results reveal that the proposed FEBIA perform better than the two population-based algorithms, demonstrating the potential of the FEBIA to solve the unrelated parallel machine problem with periodic maintenance and job release times.

Keywords

• Unrelated parallel machine
• makespan
• flexible maintenance
• scheduling