A novel BRKGA for the customer order scheduling with missing operations to minimize total tardiness

Abstract

We introduce a new variant of the customer order scheduling problem with missing operations to minimize total tardiness. This problem arises in the pharmaceutical industry, more specifically in physical–chemical analysis processes. Since each sample must be processed in some specific machines, we have missing operations. Given the NP-hardness of the problem, we present approximate algorithms to solve large-sized instances. First, we propose an innovative size-reduction matheuristic for a scheduling problem with due dates. This approach is based on partitioning the decision variables considering due dates and a dispatch rule. Furthermore, we develop a novel Biased Random Key Genetic Algorithm (BRKGA) that considers an efficient local search as 2-opt best improvement with swap neighborhood and a parameter-free restart procedure which restarts the search if the quality of the worst and best solutions were equal, minimizing the amount of parameters to be defined by the BRKGA. We perform computational experiments on 640 test instances to evaluate the proposed solution approaches. The results indicate the superiority of BRKGA compared to the competitive algorithms for order scheduling and its recent variants. In all set of instances, the novel BRKGA performed better than benchmarking methods and mathematical programming models, with average relative deviation index regarding best results as lower as 0.15%. Computational results point to the capacity of the proposed approaches to solve large-sized problems.