Pattern Recognition based Lexi-Search Approach to the Variant Multi- Dimensional Assignment Problem

The Multi Dimensional Assignment Problem (MDAP) is a combinatorial optimization problem that is known to be NP –Hard. In this paper we discuss a problem with four dimensions. N jobs can be executed on Nmachines, at k facilities, using l concessions. Every job is to be scheduled on some machine at one of the facilities, using some concession. No two jobs can run on the same machine, at the same facility using the same concession. Furthermore, there is a specified maximum number of jobs that can be run at a given facility, andthere is a maximum number of jobs that can avail of a given concession. C (i, j, k, l) be the cost of allocating job ‘i’ on machine ‘j’ at facility ‘k’ using the concession ‘l’. This is provided as a 4 dimensional array. The objective is to schedule the jobs in such a way that the constraints are met and the cost is minimized. For this problem we developed a Pattern Recognition Technique based Lexi Search Algorithm, which comes under the exact methods. The concepts and the algorithm involving in this problem are discussed with a suitable numerical example. We programmed the proposed Lexi Search algorithm using C. This algorithm takesless CPU run time as compared with the existed methods, and hence it suggested for solving the higher dimensional problems.