The Coalition Formation with Spatial and Temporal constraints Problem (CFSTP)\nis a multi-agent task scheduling problem where the tasks are spatially\ndistributed, with deadlines and workloads, and the number of agents is\ntypically much smaller than the number of tasks, thus the agents have to form\ncoalitions in order to maximise the number of completed tasks. The current\nstate-of-the-art CFSTP solver, the Coalition Formation with Look-Ahead (CFLA)\nalgorithm, has two main limitations. First, its time complexity is exponential\nwith the number of agents. Second, as we show, its look-ahead technique is not\neffective in real-world scenarios, such as open multi-agent systems, where new\ntasks can appear at any time. In this work, we study its design and define an\nextension, called Coalition Formation with Improved Look-Ahead (CFLA2), which\nachieves better performance. Since we cannot eliminate the limitations of CFLA\nin CFLA2, we also develop a novel algorithm to solve the CFSTP, the first to be\nanytime, efficient and with provable guarantees, called Cluster-based Coalition\nFormation (CCF). We empirically show that, in settings where the look-ahead\ntechnique is highly effective, CCF completes up to 30% (resp. 10%) more tasks\nthan CFLA (resp. CFLA2) while being up to four orders of magnitude faster. Our\nresults affirm CCF as the new state-of-the-art algorithm to solve the CFSTP.\n