Single-machine scheduling with sequence dependent setup to minimize total weighted squared tardiness

摘要

This paper addresses the NP-hard problem of scheduling N independent jobs on a single machine with release dates, due dates, sequence dependent setup times, and no preemption where the objective is to minimize the weighted sum of squared tardiness. A Lagrangian relaxation based approach is developed for single-machine scheduling with sequence dependent setup times that is Based on a list scheduling concept in conjunction with Lagrangian relaxation. Sequence dependent setup times are formulated as Capacity constraints, and then are relaxed using Lagrangian multipliers.