The Service Delivery Scheduling (SDS) problem is an extension of the classic Job Shop Scheduling (JSS) problem, a well-known NP-hard problem in optimization even when static data are provided. SDS extends the problem domain by introducing the notion of different classes of resources to be scheduled, each with its own scheduling and availability characteristics. The telecommunications industry provides an example domain with a need to optimize SDS on an ongoing basis for scheduling the provisioning and delivery of services to customers.