A genetic algorithm for minimizing makespan of block erection in shipbuilding

Abstract

Purpose

The purpose of this paper is to propose an algorithm based on genetic algorithm (GA) to solve the block erection scheduling problem in shipbuilding.

Design/methodology/approach

The block erection scheduling problem is defined as the identical parallel machine‐scheduling problem with precedence constraints and machine eligibility (PCME) restrictions. A GA is proposed to find near optimal solution, and a few lower bounds and the percentage of the reduced makespan are defined to evaluate the performance of the proposed algorithm. Finally, the GA for block erection scheduling problem in a shipyard is illustrated by using the real data from a local shipyard.

Findings

The proposed GA produces lesser values of makespan against the random heuristic algorithm for the collected real instances.

Research limitations/implications

The proposed GA can solve other similar parallel machine‐scheduling problems with PCME to minimize makespan.

Practical implications

Based on the proposed GA, the developed scheduling system for block erection in a shipyard can reduce the makespan of block erection, and contribute to the productivity improvement.

Originality/value

The allocation of block erection to the crane is modeled as a parallel machine‐scheduling problem with PCME, and the GA is developed to solve this problem to minimize makespan.

Citation

Jinsong, B., Xiaofeng, H. and Ye, J. (2009), "A genetic algorithm for minimizing makespan of block erection in shipbuilding", Journal of Manufacturing Technology Management, Vol. 20 No. 4, pp. 500-512. https://doi.org/10.1108/17410380910953757