Metaheuristics with Neighborhood Structures for the Scheduling of Jobs with Time-dependent Durations

A scheduling problem comprising time-dependent durations, sequence-dependent setup times, batch scheduling, precedence constraints and job selection is studied. Applications of the scheduling problem could be in the testing of aircraft in a multifunctional testing facility, the distribution of resources to different areas and the repairing and maintenance of vehicles in a workshop. An integer programming formulation for this problem is presented. As CPLEX was unable to find a feasible solution for the majority of the generated test cases within one hour, metaheuristics such as variable neighborhood search and tabu search have been developed, employing eight neighborhood strategies to search for solutions. Tabu search performs the best in solving the scheduling problem. It was able to solve all test cases while CPLEX and variable neighborhood search could solve only 25% of the test cases. In terms of total weighted profit, tabu search performed 40% and 9% better than CPLEX and variable neighborhood search, respectively, for test cases solvable by all three algorithms.