Hybrid optimization algorithms by various structures for a real-world inverse scheduling problem with uncertain due-dates under single-machine shop systems

This paper investigates the single-machine inverse scheduling problem with adjusted due-dates (SISPAD) which has a strong background in practical industries. In the SISPAD, the parameters values are uncertain, and the objective is to obtain the optimal schedule sequence through minimal adjusting processing parameters or the job sequence for a promising target. First, a SISPAD mathematical model is devised to handle uncertain processing parameters and scheduling problem at the same time. Then, this paper proposes three hybrid algorithms (HVNG) that combine variable neighborhood search (VNS) algorithm and genetic algorithm by using series, parallel, and insert structure for solving the SISPAD. In the proposed HVNG, a well-designed encoding strategy is presented to achieve processing operator and job parameter simultaneous optimization. To improve the diversity and quality of the individuals, a double non-optimal scheduling method is designed to construct initial population. Compared to the fixed neighborhood structure in regular VNS, a dynamic neighborhood set update mechanism is utilized to exploit the potential search space. In addition, three different neighborhood structures are used in the HVNG algorithm. Finally, two set public problem instances are provided for the HVNG algorithm. Empirical studies demonstrate that the proposed algorithm significantly outperforms its rivals.