We study task-allocation problems where one wants to minimize the team cost subject to the constraint that each task must be executed by a given number of cooperative agents simultaneously, called the coalition for this task. We use the same principle to develop several efficient and effective (greedy) hillclimbing strategies for determining both which agents belong to the coalition for each task and when the coalition should execute the task. We analyze their complexities and compare them experimentally with each other and a previous algorithm on multi-agent routing problems.