Simulated annealing for parallel machine scheduling with split jobs and sequence-dependent set-ups

In this research, we study the problem of scheduling n independent jobs non-preemptively on m parallel machines. Each job j has a processing time and a deadline, the time at which the job must be completed. The jobs may be split into lots. For each lot, a constant set-up time is required before the first item of the lot is processed on each machine. A schedule stipulates the number of lots for each job, the lot size, the sequence of the lots on machines, the start, and the finish time of each lot. The objective is to find a schedule that minimizes the total tardiness. The problem studied here is NP-complete; consequently, optimal solutions cannot be obtained even for problems of reasonable size. Our computational work here, however, shows that using a simulated annealing SA methodology can produce a nearly optimal solution to practical sized problems.