Makespan minimization of a flowshop sequence-dependent group scheduling problem

作者：Salmasi Nasser; Logendran Rasaratnam^*; Skandari Mohammad Reza

来源：International Journal of Advanced Manufacturing Technology, 2011, 56(5-8): 699-710.

DOI：10.1007/s00170-011-3206-9

• Sequence-dependent group scheduling
• Integer programming
• Meta-heuristics
• Lower bound
• Flow shop scheduling

The flowshop sequence dependent group scheduling problem with minimization of makespan as the objective (F(m)vertical bar fmls, S(plk), prmu vertical bar C(max)) is considered in this paper. It is assumed that several groups with different number of jobs are assigned to a flow shop cell that has m machines. The goal is to find the best sequence of processing the jobs in each group and the groups themselves with minimization of makespan as the objective. A mathematical model for the research problem is developed in this paper. As the research problem is shown to be NP-hard, a hybrid ant colony optimization (HACO) algorithm is developed to solve the problem. A lower bounding technique based on relaxing a few constraints of the mathematical model developed for the original problem is proposed to evaluate the quality of the HACO algorithm. Three different problem structures, with two, three, and six machines, are used in the generation of the test problems to test the performance of the algorithm and the lower bounding technique developed. The results obtained from the HACO algorithm and those that have appeared in the published literature are also compared. The comparative results show that the HACO algorithm has a superior performance compared to the best available algorithm based on memetic algorithm with an average percentage deviation of around 1.0% from the lower bound.

• 出版日期2011-9