Multi-product unrelated parallel machines scheduling problem with rework processes

In this paper, we addressed a multi-product unrelated parallel machines scheduling problem with the possibility of producing imperfect jobs. Rework processes in the problem are studied and a Mixed-Integer Nonlinear Programming (MINLP) model to formulate this problem is proposed. Rework activities are used to upgrade imperfect jobs to a preset standard quality level. It is assumed that the defective production probability for each job on machines can be estimated through historical data acquisition. Since the problem is strongly NP-hard, exact algorithms are inefficient for medium and large-sized problems. Thus, some heuristic methods focusing on the rework processes are developed based on dispatching rules. In order to evaluate the efficiency of the presented algorithms, makespan is used as the objective function. Computational experiments show the efficacy of the modified shortest processing time (MSPT) heuristic, in terms of computational time and objective value for randomly generated test problems.