An Introduction to Algorithms for Solving Schedule-Related Problems

The Project.net project management system contains a scheduling engine that can automatically schedule the tasks in a project, determining the start and finish times of each task based on its work, duration, assigned resources, dependencies on other tasks, and other constraints.  To understand how the scheduling engine works, it's helpful to start out with a much broader perspective, and look at

  • schedule-related problems in general (which include project scheduling problems)
  • the various kinds of algorithms used to generate solutions for those problems

This article aims to provide an introductory overview of the terminology and approaches used in applying these algorithms to a wide range of classical schedule-related problems.   Later articles in this series explore the various problems and algorithms in more details, especially as they apply to Project.net's scheduling engine.

Integrated Computer Solutions is a leading developer of algorithms and products for solving schedule-related problems, notably as used in the scheduling engine for Project.net.

1. Schedule-Related Problems

Automatic Scheduling, when used properly, is one of the most powerful tools for improving the efficiency and cost of project management, planning, or manufacturing.  Scheduling can be used for long-term planning involving multiple projects to detailed planning involving tasks and jobs in a day-to-day operation. The applications can vary from staff scheduling in a retail store to project management in a large company. There is a great deal of software in the market that provides solutions to scheduling problems with different types and configurations depending on its use.

The aim of an automatic algorithm for a schedule-related problem is to produce a really good (i.e. optimal or near-optimal) schedule for a set of activities and/or for the resources to be assigned to them.  This can involve

  • Scheduling: Determining the sequence of activities, and the times each one starts and finishes.
  • Assignment: The assignment of resources (e.g. people, machines) to the activities

Schedule-related problems can be divided into three categories

  • Schedule-Related Assignment Problems just focus on assignment, where the sequence and times of activities is pre-determined.  Many of these problem are known as Workforce Scheduling problems, and commonly arise from managing staff assignments in organizations such as retail stores and hospitals, usually within a relatively short planning time horizon. These problems include Days-Off Scheduling, Shift Scheduling, and Crew Scheduling.
     
  • Scheduling-Only Problems just focus on determining the sequence and times of activities (generally known as tasks), where the assignment of resources to activities is either pre-determined or ignored.  The standard Project Scheduling problems, which focus on scheduling the tasks within a project (or related projects) fall in this category, including Basic Project Scheduling and Resource/Size-Constrained Project SchedulingBasic Portfolio Management is part of this category as well.
     
  • Joint Scheduling/Assignment Problems, where the sequence and times of activities must be determined, as well as the assignment of resources to them.  These problems include Job Shop Scheduling, Advanced Portfolio Management, and Project Scheduling with Assignment.

Schedule-related problems are part of a broader class of problems called optimization problems, which have two important features:

  • Constraints -- a formal description of the requirements that must be satisfied by a candidate solution to the problem -- for example, that a particular task can't start until some other task finishes.
     
  • Objective functions -- a mathematical characterization of the quality of a solution.  In general, an objective function aims to minimize (or maximize) some value whose calculation is based on the details of a candidate solution -- for example, minimize the time it takes to get all of the activities completed; this is a common constraint in scheduling problems, and is known more formally as minimizing the makespan.

Schedule-related problems may either be cast as offline or online problems.

  • In offline problems -- information about all activities, resources, constraints and objective functions are known in advance, and the aim is to find a single "good" solution to the problem
     
  • In online problems -- there are ongoing changes to the activities (e.g. delays, cancellations) and resources (e.g. illness, breakdown), and sometimes even to the constraints and objective functions, so that new solutions (for those activities which are not yet completed) must be continually recomputed.

2. Resource Assignment

In the simplest schedule-related problems, any resource can be assigned to any activity, but each activity has only one resource assigned to it at a time, and each resource is assigned to only one activity at a time, continuously from the time the activity starts to the time it finishes.  However, in practice, we find more complex problem formulations that have to be addressed:

  • Limited Assignments: A resource may only be assigned to an activity just for part (or for multiple parts) of the duration of the activity
     
  • Multi-Resource Assignments: An activity may have multiple resources assigned to it.
     
  • Partial Assignments: When a resource is assigned to an activity, they may only spent part of their available time working on it
     
  • Multiple Assignments: A resource may be assigned to multiple activities simultaneously (which requires support for partial assignments)
     
  • Reservations: Resources may be reserved (full or part-time) for a specific project (or group of activities), which limits how the resource can be assigned and/or when the activities pre-assigned to that resource can be scheduled.
     
  • Eligibility: An activity may only allow certain resources or types of resources to be assigned to it.
     
  • Preemption/Splitting: A resource assigned to one activity may be interrupted and assigned to another (e.g. higher priority) activity, but then may return to continue work on the initial activity.

    In online problems (especially in job scheduling), this is known as preemption, since the notion is that a higher priority activity suddenly needs to be scheduled, requiring that a resource be re-assigned to it.  In offline problems (especially in project scheduling), this is known as activity or task splitting.
     
  • Non-renewable Resources: Non-renewable resources resources (e.g. money, chemicals, etc) can be used up, unlike people who can be assigned as long as they are available.  So schedules need to be found that don't require more of the resource than is available.  More complex formulations involve partially-renewable resources and constraints.

3. Optimal & Heuristic Algorithms

Algorithms exist that can find an optimal solution (one which produces the minimum/maximum value of the objective function) in a "reasonable" time (relative to the size of the problem) for the very simplest schedule-related problems -- in particular, for simple versions of workforce scheduling and basic project scheduling.

However, for almost all of the schedule-related problems we've mentioned, optimal algorithms simply take too long, for all but but the smallest size problems.  So for most of these problems, we need to use heuristic algorithms, which can produce solutions which are near-optimal, that is, reasonably close to the optimal solution, in a reasonable amount of time.

There are a number of common heuristic approaches to algorithms used for addressing schedule-related problems, which can be divided into

  • Construction Algorithms (including Greedy Algorithms), which start with an empty or incomplete solution (e.g. where no tasks are scheduled and/or no resources are assigned), and incrementally make it more complete (e.g. by scheduling one additional task and/or assigning one additional resource at a time)
     
  • Search Algorithms, which start with one or more complete candidate solutions, and incrementally combine and/or modify them with the goal of generating better complete solutions.  These include approaches (also called metaheuristics) such as Hill Climbing, Tabu Search, Simulated Annealing, Particle Swarm Optimization, Artificial Bee Colony Algorithms, Genetic Algorithms, and Differential Evolution,.
     
  • Hybrid Algorithms, which use a combination of construction and search-based approaches

Ellis Cohen
Jarurat Ousingsawat
Project.net
January 2015