Title: Lexi-search algorithm for one to many multidimensional bi-criteria unbalanced assignment problem

Authors: Jayanth Kumar Thenepalle; Purusotham Singamsetty

Addresses: Department of Mathematics, School of Advanced Sciences, VIT, Vellore-632014, Tamil Nadu, India ' Department of Mathematics, School of Advanced Sciences, VIT, Vellore-632014, Tamil Nadu, India

Abstract: This paper deals with one-to-many multidimensional unbalanced assignment problem with two conflicting objectives, where the first objective minimises the total processing time and the other maximises the overall productivity/profit on performing n jobs by m (m <n) persons at h distinct time horizons. It is assumed that each job is operated by exactly one person, whereas a person is permitted to perform more than one job at distinct time horizons. This problem is modelled with binary programming, and has potential applications in scheduling, timetabling, human resource allocations, etc. An efficient pattern recognition technique-based Lexi-search algorithm (LSA) is developed, which is capable of enumerating the Pareto optimal solutions. A comparative study is performed between the LSA and genetic algorithm (GA) on the relaxed version of the present model. The descriptive statistical analysis of CPU runtime of LSA on distinct random instances indicates that it is taking reasonably less computational runtime.

Keywords: multidimensional bi-criteria unbalanced assignment problem; Lexi-search algorithm; pattern recognition technique.

DOI: 10.1504/IJBIC.2019.103592

International Journal of Bio-Inspired Computation, 2019 Vol.14 No.3, pp.151 - 170

Received: 22 Aug 2017
Accepted: 13 Aug 2018
Published online: 13 Nov 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article