Introduction
The current implementation uses point stacks (e.g. December 25th/03:00). This can cause situations where two different trips that touch the same day are not contained within the same stack. For example, a crewmember wants trip B instead of trip A and both are on the same day; however, trip B is not contained within the same stack. In this case, trip B would not be considered.
A new approach to handle this will have the N-PBS Scheduler expanded to offer an additional type of stack selectable at run time: day stacks. This new type of stack will be more familiar to crewmembers, as you are guaranteed that all trips that touch a given day will be in that day’s stack.
Another feature of the current system is related to the order in which stacks are considered for processing. Currently, once a stack has triggered, it is applied in a pre-selected manner (generally chronologically). A change to the N-PBS Scheduler would be to remember the order in which the stacks trigger the first time (a good indication of which days will be problematic) and use that same order in subsequent passes as the Stack Force Order.
Different Stack Types
The system currently uses a single type of stack: the Point Stack. This type of stack centers around a specific date/time (e.g. December 25th/02:00) and contains all pairings that either touch the date/time or are pairwise illegal with everything else in the stack. The problem is that two pairings that start the same day may not be contained within the same stack.
For example, suppose you have the following three pairings:
J2001/15 (15Dec/13:00 – 16Dec/10:00)
J2002/16 (16Dec/13:00 – 16Dec/20:00)
J2003/16 (16Dec/22:00 – 17Dec/10:00)
A stack centered around 16Dec/02:00 would contain J2001 as it touches 16Dec/02:00. It would also contain J2002. There is not enough rest between J2001 and J2002, so it is pairwise illegal with everything in the stack. However, J2003 would not be contained within the stack as it is only pairwise illegal with J2002 but not J2001.
This situation creates confusion for crewmembers when they bid for pairing J2003/16, but are unstacked pairing J2002/16 which matches none of their bids. The solution is to offer an additional type of stack for those customers who wish to reduce confusion with minimal degradation in run convergence. This new stack is a Day Stack.
Day Stacks
Day stacks will differ in that they will cover the full calendar day and contain all pairings that touch the day in some manner. It is not required that all pairings in the stack are pairwise illegal with each other. For example, a pairing may end at 2am on the 25th and another pairing may begin at 10pm on the 25th. In a day stacks model, both pairings will be in the 25th stack.
Pairwise Illegalities and Stacks
Currently for Point Stacks, the system includes pairwise illegal pairings within the stack. These pairings contribute to the stack height. If a crewmember takes one of these pairings, they cannot take one that actually touches the day. For example, suppose there are 15 crewmembers left; 15 pairings touch the 25th and 5 pairings that cannot be awarded at the same time as any trips on the 25th. In this situation, there will be at least 5 trips in open time.
With pairwise illegalities included in a stack, the system would have started unstacking with 20 crewmembers left and all 20 trips would have been awarded.
However, for some crewmembers, being unstacked on a day that is not directly from the day a stack represents can be confusing. What the system will offer is the ability to select whether or not pairwise illegals are used within a point stack. The administrator can then better balance admin constraint satisfaction versus crewmember perceived satisfaction.
In the context of day stack processing, pairwise illegalities will not be included in the stacks nor will an option to include them be offered. By definition, all pairings that touch a given day are included in that day’s stack. Not all of these pairings are pairwise illegal with each other. For instance, you could have a pairing ending at 2am on the 25th and another pairing starting at 10pm on the 25th. It does not make sense to add additional pairings that are considered pairwise illegal with everything in the stack, when everything in the stack is not pairwise illegal with itself.
Run Template Changes
The ability to choose whether to use a point stack or a day stack, and whether to use pairwise illegals, will be offered to the user through the run template. This will allow an administrator to customize on a run by run basis. If Day Stacks are selected, the Use Pairwise Illegals checkbox will become greyed out.
The default value for a new template will have Point Stacks selected and Use Pairwise Illegals checked. These default values will ensure the system behaves initially the same as before the change.
Derived Stack Force Order
Excluding the Priority Stack Date, the current stack force order is chronologically ordered from earliest to latest. The downside is that chronologically earlier stacks may not be the stacks in the most need of unstacking. The derived stack force order method is being introduced to mitigate this problem.
Algorithm
The idea behind a derived stack force order is that the stacks that trigger first are more apt to be in need of unstacking and thus should be processed first. The system will remember the order in which each stack is triggered the first time, regardless of which pass it was triggered in. This order will then be used to determine the application of triggered stacks.
Example demonstrating the derived stack force order’s construction over 3 passes:
Priority Stack Date
Customers currently make use of a Priority Stack Date (PSD) if a particular date is known in advance to cause unstacking issues. For example, December 25th is most likely to be preferred off or otherwise avoided due to Christmas. The PSD option makes this date the first to be unstacked in any given stack force order. This does not necessarily mean that the PSD(s) will trigger first, but it means that once they have all triggered, they will be the first stack(s) to be forced on each remaining crewmember. This helps to ensure that the date is forced on a contiguous block of junior people.
The new derived stack force order method will still make use of a PSD. Under the current system, any stack that contains at least one pairing touching the PSD will be given priority at the front of the stack force order. This occurs regardless whether the date in the stack is centered on touches the PSD.
With the derived stack force order change, the method for determining what stacks touch the PSD will change. If the date in the stack is centered on touches the PSD, it will then be included. Outlier stacks that do not touch the PSD but may contain a few pairings that do will be given no special priority.
Any stack that touches the PSD (as defined above) will be given priority to be at the front of the stack force order. Within the PSD stacks, the system will still organize them using a derived stack force order: that is, they will be processed in the order in which they first triggered.
The next example will use point stacks to demonstrate the PSD based derived stack force order vs. the regular derived stack force order: