GENETIC ALGORITHM BASED ITERATIVE TWO-LEVEL ALGORITHM FOR RESOURCE ALLOCATION PROBLEMS AND APPLICATIONS

摘要

This study concerns the resource allocation problem that involves complicating constraints and cannot be solved using correction operations of a genetic algorithm (GA). A GA-based iterative two-level algorithm is developed to solve this problem by decomposing it into master and slave problems, such that the complicating constraint function is treated as the objective function of the slave problem, which can be solved by GA, and the master problem, which includes the complicating constraint, is solved using a bisection method that is based on the optimal objective value determined in the slave problem. An example of the application of the proposed algorithm is the minimum time slot assignment problem (MTSAP) associated with a radio frequency identification (RFID) system. The GA that is utilized to solve the slave problem of the MTSAP has special features. The proposed algorithm is tested by applying it to the MTSAPs of four reader networks and many runs are performed for each MTSAP. The obtained solution to each MTSAP is optimal. The proposed algorithm is compared with a simulated annealing (SA) method. The comparison reveals that the proposed algorithm outperforms the SA method in terms of the optimality of the obtained solutions and computing speed.