Simulated annealing for parallel machine scheduling with split jobs and sequence-dependent set-ups Academic Article uri icon


  • In this research, we study the problem of scheduling n independent jobs non-preemptively on m parallel machines. Each job 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. INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING.

published proceedings

  • International Journal of Industrial Engineering : Theory Applications and Practice

author list (cited authors)

  • Diaz-Santillan, E., & Malav, C. O.

complete list of authors

  • Diaz-Santillan, E||MalavĂ©, CO

publication date

  • March 2004