The Scheduling Algorithm

Originally, the scheduling module of Outperform Planning only contained (and still contains) the so-called changeover algorithm. This is a very basic algorithm which only minimizes the sum of changeover durations. It reshuffles the order of the activities per resource and day and does not move an activity to another resource or day. It is not suitable for most of the scheduling problems our clients face today.

Therefore, the scheduling module nowadays contains a new default algorithm: The local search scheduling algorithm. This algorithm is based on a local search metaheuristic:

Create initial solution representation and store it as "current"
Initialize "best" (the best solution representation found so far) with "current"
Repeat
    Find all solution representations similar to "current" aka the neighbors of "current" (therefore the algorithm is named "local search")
    Ignore some neighbors
    Pick a neighbor (e.g. the best remaining) and make it the new "current"
    if "current" is better than "best", update "best" with "current"
Until termination criterion reached, e.g. time limit, iteration limit, …
return "best"

Solution representation vs. solution

It is quite difficult to define all similar schedules (solutions) of a given schedule (solution), especially while maintaining feasibility.

A quite “natural” approach to define the neighbors of a given schedule is to move an activity to another feasible resource and/or shift it forward or backward in time.

Moving one activity to another resource likely creates an overlap with activities already planned on the new resource, or a capacity overload on the new resource. On the other hand, when shifting an activity in time, what are the exact time spans? 5 minutes, 9 minutes, 23.5 minutes, 5 hours, 3 days? This definition can result in a lot of neighbors just for one activity to move. And there can be dozens or hundreds of activities in a schedule! And it is risky to limit the potential changes to something like “multiples of 5 minutes up to an hour,” because the algorithm may miss a more optimal solution.

Therefore, a list of all activities to be scheduled in a specific order is known as a solution representation.

Initial solution representation

Starting with a workable solution representation often helps to reduce runtimes while finding a good solution. Therefore, the initial ordering in the solution is determined by the active constraints and objectives.

First, the activities are ordered according to the constraints, e.g. if the constraint “Observe earliest start” is active, the activities are ordered by their ascending earliest start. In case two activities have the same earliest start (or no earliest start at all), the objectives are taken into consideration, ordered by priority, to resolve these ties. For instance, if the highest priority is to minimize tardiness, the activities with a tie with respect to earliest start are further ordered by their latest end. If that is still not sufficient, an objective with the next lower priority is used to resolve the tie, and so forth.

If neither constraints nor objectives are able to resolve the tie between two activities, then the ERP code of the underlying production order is used as a tiebreaker. If that is not sufficient, the internal ID of the order is used as the final tiebreaker.

Transform, evaluate, and compare

The algorithm's ultimate goal is to find the best or, at least, a very good solution. To find such a representation, you must be able to decide which of two given representations is better, i.e. you need to compare them with respect to one or more given configurable objectives.

An objective (e.g. minimize the total changeover time) assigns a value (here: the total changeover time) to a given solution. The solution with the better (here: smaller value) is the better one. As stated, we need a solution, not a solution representation to calculate the objective value.

To transform a solution representation into a solution, we schedule the solution representation's activities, i.e. assign a resource, BoM and start time to each activity. The sequence of the activities is given by two factors. First, they are separated into four blocks. Block 1 is made up of the activities for which the algorithm is not allowed to neither change the resource or the start time. Block 2 includes activities where the algorithm is only allowed to change the resource. Block 3 includes activities where the algorithm is only allowed to change the start time. Finally, Block 4 is made up of activities where the algorithm is allowed to change both the resource and the start time. In each block, the activities are ordered according to the given order in the solution representation and the four blocks are re-concatenated. The restrictions observed during the actual transformation are user configurable (e.g. don't change the proposed resource or don't violate the earliest start time). Each activity is planned the best way according to the given objective(s), observing the already scheduled activities.

During this process, there is no backtracking: if the current activity B could be planned better if activity A would have been planned differently before leading to a better schedule: tough luck. There will be other solution representations to be transformed and evaluated where activity B will be planned before activity A, and such a solution representation will lead to a better overall schedule.

Once all activities are scheduled, the transformation of a solution representation into a solution is complete.

The neighborhood of a solution representation

A neighbor of a given solution representation is created by swapping two adjacent activities in the list where the first and the last activity in the list are also considered “adjacent." This leads to as many neighbors as activities in the list. For instance, a list of 4 activities, ordered as 1234, has 4 neighbors: 2134, 1324, 1243 and 4231. The process of creating a neighbor is called a “move," the set of all neighbors of a given solution representation is called its “neighborhood."

The following pictures shows all elements of the process:

Not every neighbor in a neighborhood is a candidate to be picked and to become the new “current." Examples for such neighbors are neighbors already visited earlier or neighbors not better than the “current."

From the remaining neighbors, one neighbor (the best one with respect to the objectives) is picked to become the new “current."

Excluding too many neighbors can restrict the neighborhood quite substantially, even up to an empty neighborhood. Then the current solution representation is a local, but not necessarily a global optimum, as there are no neighbors left to pick from. There are various techniques to circumnavigate this situation. this scheduling algorithm uses Simulated Annealing.

In Simulated Annealing, the algorithm is allowed to pick a worse neighbor with a certain probability. The probability depends on two factors: how early in the search the worsening occurs and the relative size of the worsening. The smaller the worsening and the earlier in the search process, the more likely the algorithm is to pick such a neighbor. In other words: at the beginning of the search process the algorithm allows for big worsening to be able to reach a completely different solution (after a few more steps). However, later in the process the algorithm should converge to a local and hopefully global optimum and ideally should not be “disturbed” on the way to it.

The building blocks of the local search scheduling algorithm

Input

The transactional input to scheduling comes from three sources:

• Production orders in the ERP system
• Production proposals from the consolidated plan.
• The current schedule, which includes downtime activities.

Constraints

Constraints limit the options the scheduling algorithm has when creating its output; each of them can be activated or deactivated individually.

• Keep BoM: the activities created from the input (see above) may have a (suggested) BoM assigned. If that’s the case, the scheduling algorithm may not change it.
• Keep date: the activities created from the input (see above) may already have a (suggested) production date assigned. If that’s the case, the scheduling algorithm may not change it.
• Keep number of enablers: the activities created from the input (see above) may have a (suggested) number of enablers assigned. If that’s the case, the scheduling algorithm may not change it.
• Keep resource: the activities created from the input (see above) may have a (suggested) resource assigned. If that’s the case, the scheduling algorithm may not change it.
• Observe earliest start: if an activity has an earliest start defined, any production start before this time is not allowed. The preceding changeover may start before the defined earliest start.
• Observe latest end: if an activity has a latest end defined, any production end before this time is not allowed. The succeeding changeovers may end after the defined latest end.
• Observe supply calendar: an activity may only be scheduling to a day marked as active for the respective location of the resource and product produced by the BoM.

Objectives/Goals

The objectives, also known as goals, guide the algorithm when defining how a good solution should look like. The most important objective is to schedule as many activities as possible. The other objectives, selected by the user, define “what is a good resource and a start time for the activity on hand to allocate to and schedule, respectively?” Each objective’s calculation results in a single number, the smaller a result the better. When converting to a number, any duration is considered in hours. Each of the objectives activated must have a priority (a positive integer) and a weight (a positive decimal) assigned. The lower the priority number assigned, the higher the objective’s priority is and the more influence the objective has on the algorithm’s decision. Objectives with identical priorities use the weight to determine their relative influence on the algorithm; a higher weight means higher influence.

• Makespan: the maximum over all resources of the difference between the last and the first moment of resource usage by changeover and/or production. This prefers solutions without idle time between two activities.
• Total changeover: the sum of all changeovers on all resources
• Total squared changeover: analogously to “Total changeover”, but with the changeover durations squared before summed up. This prefers a solution with many small changeover durations over a solution with a few big changeover durations.
• Total changeover hours of enabler usage: the sum of all changeovers multiplied by the enablers assigned to the related production activity.
• Total earliness: the sum of all activities’ earliness of production start, i.e., the time range an activity’s production starts before the associated earliest start. A production start after the related earliest start does not count as a bonus.
• Total production hours of enabler usage: the sum of all production hours multiplied by the enablers assigned to the related production activity.
• Total slack to deadline: the sum of all activities’ earliness of production end, i.e., the time range an activity’s production ends before the associated latest end. A production end after the latest end does not count as a bonus.
• Total tardiness: the sum of all activities’ tardiness of production end, i.e., the time range an activity’s production ends after the associated latest end. A production end before the latest end does not count as a bonus.
• Total squared tardiness: analogously to “Total tardiness”, but with the tardiness values squared before summed up. This prefers a solution with many small tardiness values over a solution with a few big tardiness values.

In the companies and industries that Outperform serves, making an operationally feasible schedule, i.e. observing the given constraints, in a short amount of time is the primary goal; optimality as defined by the objectives is subordinate to that.

Output

From this input, the algorithm then:

• Tries to allocate each activity to a resource and assign a start time as good as possible with respect to the selected objectives and observing the active constraints.
• Works out the accurate durations for the activities for the productive time.
• Observes the given downtimes.