FDA PERFORMANCE ANALYSIS OF JOB SHOP SCHEDULE IN UNIFORM PARALLEL MACHINES
The challenging problem of a non-homogeneous machine load planning is to distribute jobs to the different machines with the same ability at the operation for the minimum cost. Each operation can be performed by a set of machines with the same or different characters, and each machine can handle a job many times with different operations. A new heuristics method (FDA, Four Dimension Algorithm) for uniform parallel machine scheduling is proposed in this paper to tackle this load distribution problem. The FDA method is to select a sequence, a machine set and an operation such that the minimum evaluation of the defined indexes is achieved. These indexes consist of four independent parameters. Essentially, this method consists of three main iteratives in implementation: iterative for job numbers, iterative for the operation turns and iterative for the non-homogeneous machines. Each operation is associated with a set of evaluation indexes. The proposed algorithm has shown a significant improvement over Genetic Algorithm and Branch and Bound Algorithm. The key of this new method is partial indexes calculated in every cycle only. As a result, the complexity of this method is greatly improved from exponential to only polynomial (O(mn + 3m (2)n(2)) at most). The most noticeable innovation in this proposed method is the practical efficient algorithm capable of analyzing non-homogeneous machine and job relations while reducing complexity of computation. Of equal importance, a various examples and experiments are shown in detail.
fda uniform parallel job-shop doe scheduling algorithm