Bilevel time minimizing assignment problem

摘要

In this paper, a bilevel time minimizing assignment problem is studied in which the aim is to find an optimal partition of the set of n facilities into two mutually disjoint subsets L1 and L2 where, L1 contains m facilities called Level-I facilities and L2 contains the remaining (n − m) facilities termed as Level-II facilities. The partition is to be optimal in the sense that for this partition the sum of the completion times of the jobs assigned to Level-I and Level-II facilities is the least. It is assumed that all the jobs are to be done, each facility works only on one job, and on each job only one facility works. Further Level-II facilities start working simultaneously on their respective assigned jobs only after Level-I facilities, working in parallel, have finished their jobs. For a feasible assignment TL1(·) denotes the completion time of the jobs assigned to Level-I facilities and TL2(·) that of the jobs assigned to Level-II facilities. Depending on m is greater or smaller than (n − m), the pairs of the type ((TL1(·),TL2(·)):TL1(·)⩾TL2(·)) and ((TL1(·),TL2(·)):TL1(·)⩽TL2(·)) of the completion times of the jobs assigned to Level-I and Level-II facilities are generated and an optimal partition of the set of n facilities is determined corresponding to the pair for which TL1(·)+TL2(·) is the least. To obtain the global minimizer of the proposed problem, a polynomial time algorithm is presented which has been coded in C++ and an empirical analysis has been carried out with the help of randomly generated test problems.