The existing shelf space allocation methods only optimize the profits without considering the sales time. Actually, the time to sale the products is important as well to retailers because the time has a significant impact on the liquidity and long-term profits of a retail shop. Hence, this paper proposes a bi-objective model, in which one objective is to maximize the total profits of all store's products whereas the other objective is to minimize the total time to sale the store's products. By transforming this model into a single objective problem, we optimize the shelf space allocation problem in terms of the retail profits and sales time using a hybrid genetic algorithm (GA), in which three improved local search methods are designed to improve the GA performance on local search. Further, the new multi-criteria selection scheme is also designed to maintain diversity of population. The experimental results show that the proposed model outperforms the existing method in terms of profit per unit time.