This research designs a combinatorial auction mechanism under execution uncertainty to satisfy incentive compatibility, individual rationality, and efficiency by leveraging bonus and penalty. A buyer posts a task composed of multiple sub-tasks to be outsourced. If temporal and precedence relations exist among sub-tasks, then the buyer specifies them. The buyer may also specify a time interval within which all the sub-tasks should start and finish. Suppliers submit multiple bids composed of their interested sub-tasks, prices, and schedules for those selected sub-tasks. This research formulates a winner-determination problem, which is based on bid prices and suppliers’ success probabilities in delivering the sub-tasks, and suppliers’schedules. Under a combinatorial mechanism for tasks with dependencies and combinatorial valuations, a supplier can be penalized based on his or her failures, or the supplier can be rewarded on the basis of other suppliers’ successes. In this manner, the issue of fairness predominates. This research also designs an economically fair mechanism that specifies bonuses and penalties depending on the outcomes of sub-tasks. The research shows that total payment under the designed mechanism is bounded above by the buyer’s valuation of the task.