A new algorithm for complex product flexible scheduling with constraint between jobs

In order to simplify the complex product flexible scheduling problem with constraint between jobs, a new hierarchical scheduling algorithm based on improved processing operation tree is presented. Aiming at the routing problem, short-time strategy and machine-balance strategy are adopted to assign each operation to a machine out of a set of machines. And in order to solve the sequencing problem, the allied critical path method is first adopted to confirm the scheduling sequence of operations, and then operations are divided into dependent operations and independent ones according to their characteristics. For the dependent operations, forward greedy rule is adopted in order to make the completion time of operation as soon as possible and the scheduling algorithm of shortening idle time is adopted by analyzing the characteristics of the independent operations. Experiment shows that the proposed algorithm solves for the first time the complex product flexible scheduling problem with constraint between jobs. (C) 2009 Elsevier Ltd. All rights reserved.