2006b) Constructive and simulated annealing heuristics for hybrid flow shops with unrelated parallel machines

Most scheduling problems are combinatorial optimization problems which are too difficult to be solved optimally, and hence heuristics are used to obtain good solutions in reasonable times. The specific goal of this paper is to investigate scheduling heuristics to seek the minimum of a positively weighted convex sum of makespan and the number of tardy jobs in a static hybrid flow shop environment, where at least one production stage is made up of unrelated parallel machines. In addition, sequence- and machine- dependent setup times are considered. Some simple dispatching rules and flow shop makespan heuristics are adapted for the sequencing problem under consideration. The improvement heuristic algorithm proposed is a reinsertion algorithm. A simulated annealing algorithm is presented in this paper. Three basic parameters (i.e., cooling schedules, neighborhood structures, and initial temperatures) of a simulated annealing algorithm are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages