Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem

Date

2020-05-30

Advisors

Journal Title

Journal ISSN

ISSN

0956-5515

Volume Title

Publisher

Springer

Type

Article

Peer reviewed

Yes

Abstract

In this paper we focus on an unrelated parallel workgroup scheduling problem where each workgroup is composed of a number of personnel with similar work skills which has eligibility and human resource constraints. The most difference from the general unrelated parallel machine scheduling with resource constraints is that one workgroup can process multiple jobs at a time as long as the resources are available, which means that a feasible scheduling scheme is impossible to get if we consider the processing sequence of jobs only in time dimension. We construct this problem as an integer programming model with the objective of minimizing makespan. As it is incapable to get the optimal solution in the acceptable time for the presented model by exact algorithm, meta-heuristic is considered to design. A pure genetic algorithm based on special coding design is proposed firstly. Then a hybrid genetic algorithm based on bin packing strategy is further developed by the consideration of transforming the single workgroup scheduling to a strip-packing problem. Finally, the proposed algorithms, together with exact approach, are tested at different size of instances. Results demonstrate that the proposed hybrid genetic algorithm shows the effective performance.

Description

The file attached to this record is the author's final peer reviewed version. The Publisher's final version can be found by following the DOI link.

Keywords

Unrelated parallel machine problem, Workgroup scheduling, Twodimensional bin packing problem, Heuristic strategy, Genetic algorithm

Citation

Su, B., Xie, N. and Yang, Y. (2020) Hybrid genetic algorithm based on bin packing strategy for the unrelated parallel workgroup scheduling problem. Journal of Intelligent Manufacturing.

Rights

Research Institute

Institute of Artificial Intelligence (IAI)