Lagrangian Relaxation Algorithm for a Single Machine Scheduling with Release Dates

The paper considers a single machine scheduling problem with release dates to minimize the total completion times of jobs. The problem belongs to the class of NP-hard. We present a mixed-integer linear programming formulation based on slot idea. The original problem becomes an allocation problem where the main model decisions define the assignment of the time slot at which every job to be processed on a single machine. Lagrangian relaxation (LR) is proposed to solve the problem. Due to slot-based modeling, the application of LR in our problem can be extended to solve the problem with continuous-time variables, which is always confined to be used to the problem with discrete-time variables. Lagrangian-based heuristic consists of two phases: construction procedure and improvement procedure, which is based on pair-wise interchanges and kick strategy. Computational results show the Lagrangian-based heuristic is effective. The quality of the upper bounds obtained from the Lagrangian-based heuristic is advisable for the small size problem since the best feasible solutions generated are closed to the optimal values obtained by CPLEX.