A heuristic algorithm for scheduling in a flow shop environment to minimize makespan

International Journal of Industrial Engineering Computations

关键词: Flow-shop;    Heuristics;    Makespan;    Scheduling;    Benchmark Problems;   

DOI  :  10.5267/j.ijiec.2014.12.002

来源: DOAJ

【 摘 要 】

Scheduling ‘n’ jobs on ‘m’ machines in a flow shop is NP- hard problem and places itself at prominent place in the area of production scheduling. The essence of any scheduling algorithm is to minimize the makespan in a flowshop environment. In this paper an attempt has been made to develop a heuristic algorithm, based on the reduced weightage of ma-chines at each stage to generate different combination of ‘m-1’ sequences. The proposed heuristic has been tested on several benchmark problems of Taillard (1993) [Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278-285.]. The performance of the proposed heuristic is compared with three well-known heuristics, namely Palmer’s heuristic, Campbell’s CDS heuristic, and Dannenbring’s rapid access heuristic. Results are evaluated with the best-known upper-bound solutions and found better than the above three.

【 授权许可】

Unknown