Workflow balancing in parallel machine scheduling with precedence constraints using genetic algorithm

Abstract

Purpose

To propose a methodology based on genetic algorithm (GA) to solve the parallel machine scheduling problems with precedence constraints.

Design/methodology/approach

Workflow balancing helps to remove bottlenecks present in a shop floor yielding faster movements of components or jobs. Multiple machines are used in parallel for processing the jobs to meet the demand. In parallel machine scheduling with precedence constraints, there are m machines to which n jobs are assigned using suitable scheduling algorithms. Workflow of a machine is the sum of processing time of all jobs assigned. All the preceding jobs are allocated first to satisfy the constraints. GA is developed to solve parallel machine scheduling problems with precedence constraints based on the objective of workflow balancing. The GA was coded on IBM/PC compatible system in the C++ language for simulation to a standard manufacturing environment.

Findings

The relative percentage of imbalance (RPI) in workloads among the parallel machines is used to evaluate the performance of the GA developed. The proposed GA produces lesser RPI values against the RANDOM heuristic algorithm for a wider range of jobs and machines.

Research limitations/implications

The performance of GA can be compared with the performance of other meta‐heuristic algorithms to find out the robustness of the results obtained by this research.

Practical implications

The proposed GA also gives better solution for a case study of assembly scheduling.

Originality/value

The allocation of assembly operations to the operators is modeled into a parallel machine scheduling problem with precedence constraints using the objective of minimizing the workflow among the operators.

Citation

Rajakumar, S., Arunachalam, V.P. and Selladurai, V. (2006), "Workflow balancing in parallel machine scheduling with precedence constraints using genetic algorithm", Journal of Manufacturing Technology Management, Vol. 17 No. 2, pp. 239-254. https://doi.org/10.1108/17410380610642296