Solving single machine scheduling under disruption with discounted costs by quantum-inspired hybrid heuristics

• We study single machine scheduling under disruption with discounted costs.
• We consider both the original objective and the deviation cost.
• We design one quantum-inspired hybrid heuristic to solve the problem.
• Hybrid method outperforms NSGA-II in proximity and diversity.

In this paper we study machine disruption on scheduling problem. We focus on the case where the weighted discounted shortest processing time (WDSPT) rule is optimal for original single machine scheduling problem. After a subset of jobs have finished processing, we learn that the machine would be disrupted for some period of time in the future. Therefore a new schedule is needed considering both original objective and the deviation from the initial schedule. The original objective is measured by the weighted discounted total completion time and the deviation is measured by the variances in jobs’ completion times. According to the characteristics of optimal schedule, we design one hybrid heuristic algorithm, combining the advantages of qubit representation in quantum computing and Non-dominated Sorting Genetic Algorithm (NSGA-II). By analyzing the solutions diversity and proximity to optimal Pareto front on several metrics, we demonstrate that the proposed algorithm is effective for machine disruption management.