Optimization Approaches for a General Class of Single-Machine Scheduling Problems

We study a general class of single-machine scheduling problems with setup time/cost and no idle time in the schedule. It includes a variety of other scheduling and routing problems as special cases. A polynomial size mixed-integer linear programming (MILP) formulation is presented. A tabu search (TS) algorithm, built upon a novel composite-move neighborhood structure, is developed for solving the addressed problem effectively and efficiently.