Scheduling in a two-stage flowshop with parallel unrelated machines at each stage and shared resources

The paper deals with the problem of preemptive scheduling in the two-stage flowhop with parallel unrelated machines at both the stages and renewable resources shared among the stages. A novel heuristic is proposed which minimizes the flowshop makespan taking into account both the stages simultaneously. This heuristic introduces a new concept of the sets of jobs which are allowed to be processed at stage 1 and stage 2 in successive time intervals. The definition of these sets is based on a priority rule. The constraints resulting from this definition are included into the optimization problem solved by a column generation (CG) algorithm. The CG algorithm creates the schedule which is composed of partial schedules assigning jobs to machines for simultaneous processing at the first and second stages during some periods of time, so that the resource constraints are satisfied at any moment. We developed four heuristic algorithms which start either from a straightforward initial solution or from a solution provided by a linear programming based procedure, and use a simulated annealing or tabu search procedure to create partial schedules in each successive iteration. The results of the extensive computational experiment indicate that these algorithms provide good quality solutions with reasonable computational effort, even for the difficult problems with strong resource constraints.