Minimising makespan on parallel machines with precedence constraints and machine eligibility restrictions

作者：Hu, Xiaofeng^*; Bao, Jin Song; Jin, Ye

来源：International Journal of Production Research, 2010, 48(6): 1639-1651.

DOI：10.1080/00207540802620779

• scheduling
• parallel machine
• heuristics
• shipbuilding
• machine eligibility
• precedence constraints

The block erection problem is defined as a parallel machine scheduling problem with precedence constraints and machine eligibility restrictions. A heuristic algorithm combined of the largest total amount of processing first rule (LTAP) and the enhanced smallest machine load first rule (ESML) is proposed to minimise makespan for the block erection in a shipyard. Finally, four lower bounds and the percentage of the reduced makespan compared with the current solutions are defined to evaluate the performance of the proposed algorithm. The experiments are performed on data selected from a shipbuilding company, and the results demonstrate that the presented algorithm can effectively find a good solution to minimise the makespan of the block erection problem.

• 出版日期2010
• 单位上海交通大学