Abstract: Combinatorial auctions are efficient mechanisms for allocating resource in complex marketplace. The combination auction with XOR-bids and OR-bids allows bidders expressing their general preference more exactly. Winner determination, which is NP-complete, is the core problem in combinatorial auctions. In this paper, a zero-one programming model and a heuristic algorithm are proposed for solving the winner determination problem with XOR-bids and OR-bids. For searching the non-competitive bids in XOR-bids and OR-bids, new heuristic rules and methods are designed in the preprocessing. The heuristic algorithm is a partheno-genetic algorithm combined with the immune operator. In the immune operator, new heuristics are designed for evaluating the bids and applied in the procedure of vaccines selection and vaccination. Simulation results show that the algorithm achieves good performance in large size problems and the immune operator can improve the searching ability and increase the converging speed greatly.