Apparatus and methods are provided for scheduling services in a traffic-engineered communications network. In one aspect a method comprises: receiving a request to schedule a second service utilizing the network in a second time period, wherein the second time period overlaps a first time period in which a first service utilizing the network has already been scheduled; and computing a path for the second service through the network. The step of computing the path for the second service through the network comprises: responsive to a determination that the request is received less than the threshold period of time before the start of the first time period, disallowing the second service from pre-empting the first service.