ENUMERATIVE APPROACHES TO PARALLEL FLOWSHOP SCHEDULING VIA PROBLEM TRANSFORMATION

Flowshop scheduling arises in the chemical process industries in continuous and batch processing applications. The parallel flowshop model is defined by a set of jobs and a set of production lines on which the jobs will be processed. Each job has a particular time at which it can begin processing and a deadline by which processing must be complete. A schedule will give a specific ordering of which jobs to process on which lines. The objective is to minimize the total cost associated with the schedule. The major costs associated with each job are production costs, transportation costs, inventory costs, and setup costs. This model has the ability to address trade-offs associated with differing cost functions for each production line. These differing cost functions allow for the simultaneous optimization of several chemical plants which have disparate production and technological capabilities. A mathematical model is developed for the parallel flowshop and is transformed into a constrained traveling salesman problem. An exact algorithm is given based on implicit enumeration of the solution space. Results show that the algorithm performs well on some instances having up to 100 jobs.