Scheduling multipurpose batch process industries with no-wait restrictions by simulated annealing

Scheduling problems in multipurpose batch process industries are very hard to solve because of the job shop like processing structure in combination with rigid technical constraints, such as no-wait restrictions. This paper shows that scheduling problems in this type of industry may be characterized as multiprocessor no-wait job shop problems with overlapping operations. A simulated annealing algorithm is proposed that obtains near-optimal solutions with respect to makespan. This paper shows that the no-wait restrictions require several adaptations of the neighborhood structure used by simulated annealing. The performance of the algorithm is evaluated by scheduling industrial instances from a multipurpose batch plant in the pharmaceutical industry. Our results indicate that simulated annealing consistently gives better results for a number of realistic instances than simple heuristics within acceptable computation time.