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

Bentao Su, Naiming Xie () and Yingjie Yang
Additional contact information
Bentao Su: Nanjing University of Aeronautics and Astronautics
Naiming Xie: Nanjing University of Aeronautics and Astronautics
Yingjie Yang: Institute of Artificial Intelligence, De Montfort University

Journal of Intelligent Manufacturing, 2021, vol. 32, issue 4, No 4, 957-969

Abstract: 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.

Keywords: Unrelated parallel machine problem; Workgroup scheduling; Two-dimensional bin packing problem; Heuristic strategy; Genetic algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10845-020-01597-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joinma:v:32:y:2021:i:4:d:10.1007_s10845-020-01597-8

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10845

DOI: 10.1007/s10845-020-01597-8

Access Statistics for this article

Journal of Intelligent Manufacturing is currently edited by Andrew Kusiak

More articles in Journal of Intelligent Manufacturing from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().