Multi-level job scheduling under processing time uncertainty

Abstract This study deals with a multi-level job scheduling problem in a single machine under processing time uncertainty. For the objectives of minimizing the total weighted tardiness of orders and the schedule deviation of the realized schedule from the baseline schedule, two surrogate measures for each of the two objectives are proposed to cope with the processing time uncertainty in the baseline scheduling phase. For the suggested surrogate measures, several optimal solution properties are developed to reduce the size of the solution space. Then, by using the solution properties a heuristic algorithm with two different order prioritization rules and a metaheuristic algorithm based on the discrete particle swarm optimization are developed for the order sequencing problem. Also, an iterative job sequencing algorithm is developed for the job sequencing problem that can be used for a given order sequence. From a series of computational experiments with a number of randomly generated problem instances with multiple bills of materials and normally distributed processing times of items, it is identified that the suggested metaheuristic algorithm with or without the iterative job sequencing algorithm shows good performance compared with the heuristic algorithm.