Warning: Reading the following and implementing it in the aid of participating in Quintiq's contest (http://www.quintiqcareers.com/puzzle.html) will make your results "void".
This is a learning series that I wanted to experiment and start with. I have figured out that this project can take a lot of time and it cannot be implemented without breaking it up into multiple simpler steps. In addition, this learning series will be more of a solution sheet instead of an exercise sheet. For simplicity's sake, we are going to use the Dev C++ environment, which we will not need it this time. In addition, we will see how our design will change multiple times as we progress more within our implementation. The goal of the following series is to implement a partial part of the project and not all of it at once. Once this series is done within my blog posts, I may have considerations to reformat it in a lecture format. The inspiration to create a series of such form is out of a lecturer that handed projects in such format (only one project with multiple milestones).
The problem we are going to tackle is time scheduling. Time scheduling is one of the most challenging problems in the business world. There are two components in these days a software operation can be classified as:
- Creating a platform to input data (also referred as Enterprise Resource Planning systems)
- Creating an entity that can interact with the platform to input the best optimal solution within the system (also referred as Decision Support or Autonomous systems).
The platform we are going to create is based on Quintiq's puzzle. Before going on, if you plan to play the Quintiq's puzzle at any point of time, please read the following from the terms and conditions: "We trust that all attempts and submissions to this competition are the genuine effort of the participant alone." I never participated in this contest based on those terms and agreements. When it means "alone", it really means "alone", to not do it with the help of a computer. So reading the following and implementing it in the aid of participating in Quintiq's contest will make your results "void". There is a real reason why there is "1 hour for each attempt" and only "3 tries". This is to test your brain. There are people that can optimize their brain in solving these puzzles. This all depends on your innate abilities of processing things, the extent of practicing puzzles, and using the combination solution of other puzzles you already solved in this problem. The funny thing for me is that I cannot imagine someone to not able to replicate their "system" when they can solve this puzzle with score of 85% or more. I guess it is just my perception. In any case, the puzzle of Quintiq is nice for looking its complexity. By posting this type of series, I am currently not violating their "terms and conditions". However, you know how the "invisible law" works, right? I am in some sense giving an opportunity for someone else to violate the terms and conditions of the puzzle. However, Quintiq, I hope you understand to look at it through "other means for fair usage of educational purposes". Removing my post will only make me recreate the puzzle in a different format that does not touch your original copyrighting of your ideas, but will still be about time scheduling, and it will still be easy for someone else to change the puzzle in the format of yours to violate your terms (it will just have different rules and it will be about nurse time scheduling). I have already warned users that further reading this article will violate the term agreements of your prize contest. So think about it and hope people in faith to able to distinct these things themselves instead of aggregating the problem and imposing rules.
Rule Comments
First of all, we have to look at the main puzzle article: http://www.quintiqcareers.com/puzzle.html
Here are my comments for the rules of the game:
1. There are three bus lines: Line 1, Line 2, Line 3
2. You must allocate two drivers per line per day. One for the morning shift and one for the late shift.
Although you must allocate two drivers per line per day, it doesn’t seem that it is mandatory.
If we look at the point system of the main article, we see that for each unassigned shift, you get -20 points. In other words, it is a policy, not a rule. It is those rules “where you can get away with”. So confusing that it uses the word “must”. If we take also the following excerpt, “you take on the challenge of creating an optimum working schedule for Big Blue Buses’ drivers to cover the next 14 days.” , we can deduct that the maximum negative points you can get for this is -20*28 = -560 points and the least negative points you can get is 0 points (all 28 shifts are scheduled). We will see later there is some randomness in this puzzle. For instance, the workers can pick days off. Although this is very unrealistic for a manager to do, all the workers working in this company can take a day off,maybe for a strike or something. In that essence we will get -16 points on that day no matter what. For our program, we will allow to have unlimited days. As for each line constraints (only 2 shifts, one morning and one late), we will have them.
If we look at the point system of the main article, we see that for each unassigned shift, you get -20 points. In other words, it is a policy, not a rule. It is those rules “where you can get away with”. So confusing that it uses the word “must”. If we take also the following excerpt, “you take on the challenge of creating an optimum working schedule for Big Blue Buses’ drivers to cover the next 14 days.” , we can deduct that the maximum negative points you can get for this is -20*28 = -560 points and the least negative points you can get is 0 points (all 28 shifts are scheduled). We will see later there is some randomness in this puzzle. For instance, the workers can pick days off. Although this is very unrealistic for a manager to do, all the workers working in this company can take a day off,maybe for a strike or something. In that essence we will get -16 points on that day no matter what. For our program, we will allow to have unlimited days. As for each line constraints (only 2 shifts, one morning and one late), we will have them.
3. A driver can only do one shift per day; early or late.
Just to note, morning is early. Other than that, we take note the driver can only drive 0-14 for the next 2 weeks and he can drive the maximum one shift for one day. Our program will have those constraints.
4. There are eleven bus drivers: A, B, C, D, E, F, G, H, I, J, and K. Some are only qualified to drive on Line 1, 2 or 3, while some are qualified to drive on a combination of two of those lines. Find the qualifications under each driver name in the Shift Planning form.
This is where the randomness starts to begin. The first randomness of the puzzle is that a driver can have either one to two licenses. The second randomness is the driver’s line will be random. What if all drivers are on line 3? Then obviously, you should ensue the negative points out of it for the unassigned lines of line 1 and 2. Our program will have unlimited drivers. For this project, we will handle first to create things first only manually. Later on, we can automate the process by making the program express randomness in the scope of the statements provided in the puzzle.
5. Every driver is entitled to days off. Days off are indicated with dark gray nodes in the Shift Planning form. You can’t assign shifts on days off.
Okay, so here we have a third randomness. The number of days a driver can take days off are 0-14 and will be colored in dark gray. Those cannot be used no matter what. In other words, it is a rule.
6. Some drivers prefer to take particular days of the week off. This is indicated by light gray nodes in the Shift Planning form. These are preferences, rather than rules.
So this is the fourth randomness. The drivers can have preferences which days he prefers to have his days off. The preference of days a driver can take a day off is 0-14 days. So if you respect one of the driver’s slot, you get 4 points.
7. Drivers may prefer to work an early or late shift on particular days. The yellow nodes in Shift Planning form indicate shift preferences.
So this just accommodates preferences to work on a particular shift (fifth randomness).
8. Most drivers dislike working too many late shifts. Therefore, the late shifts should be distributed as fairly as possible among the drivers. You should aim to assign exactly 4 late shifts to each driver over the two-week planning period.
This sound confusing, but it is true. You must assign 4 night shifts for each driver. On the “How to play” section tab, see the text “Deviation target late shifts” within an image of the actual application. In addition, see on the main article points system table that says, “For every late shift assigned that is not equal to 4, you get -8 points”. What does that mean? The negative points you will get is based on the number of late shifts the driver has. The formula is |(4-X)|*(-8) where | | represents absolute value and X the number of late shifts. So in the same way we learned in algebra, the formula will change on the condition of 4-x > 0 to (4-x)*-8 and (-4+x)*-8 on the condition of 4-x < 0. So in programming terms, the calculation result of 4-x must be determined for each driver to determine what the second formula will be.
9. According to an agreement with the Transport Workers Union, a driver must not be assigned a late shift followed by an early shift the next day.
This is pretty self explanatory. How to avoid that? Well, put a different driver that had no shift the previous day or his previous shift was on day time. For each late shift followed immediately by an early shift in a single driver’s schedule, you get -30 points.
10. According to a second agreement with the Transport Workers Union, a driver can only work no more than three consecutive late shifts.
For every after the third consecutive late shift assigned to a single driver you get -10 points.
There is one thing that was not mentioned in relation to points:
- For each driver allocated a long rest (3 or more consecutive days off) + 5 points
Okay, like I said in one of my comment rules, the creation system we will create will be done all manually by the user. After that, the creation system can be done automatically with some randomness (it will just be an extra option on the main menu).
For me, Quintiq exercise is one of the most complex problems in the category of "small bursts". In real life, most of the problems in "overall" are difficult in the essence there are a lot of steps going from point A to point B. The difficulties in real life problems most of the time is maintaining and inspecting all the blocks going in the correct flow. You will rarely encounter problems in such form. However, this type of problems teach you a lot about design while seeing the results directly (while real life problems, their response of results is slow, such as the symptoms of high blood pressure). Most real life solutions biggest impact of its company value is the return of investment in the next 5-10 years instead of its short term results that accomplished for the current needs of the customer and client. For that reason, I have appreciated and respected the role of a system analyst. Most people have not concluded that the source of the problem in most software is the design of the software and less on the implementation of the program. However, I am going off topic now, and it can be discussed on another time.
After looking at the problem in Quintiq's website, we can conclude the following:
The worker has the ability to set only one of the following per day before his schedule is scheduled:
- NORMAL (N)
- PREFERDAYSHIFT (PD)
- PREFERNIGHTSHIFT (PN)
- PREFERABSENT (PA)
- ABSENT (A)
If yes, would it not made more sense if it was called "respect a day preference", instead of "single shift preference"? Also note that a driver can only do one shift per day: early or late. Also note from the excerpt "Drivers may prefer to work an early or late shift on particular days". Regardless, this is a good question to ask client or system analyst/designer about.
What are the "Prefer" codes?
They are a derived product of Normal. In other words, besides having the ability to work on that day, following their preferences (which are self explanatory by their status names), you get additional +3 points for PREFER(DAY/NIGHT)SHIFT and +4 points for PREFERABSENT.
What is "Absent" code?
Unlike the "Normal" code and its derived products (with prefix "PREFER"), you cannot set a work shift to that worker on that day no matter what.
With the Rule comments and the previous conclusion we made, we result in our first simple draft diagram
Program Flow
Command Prompt
How many days on Timetable? Input variable <days>
How many lines? Input variable <lines>
Program will show X tables (One table for each line). On each table, there will be 2Y columns (Two columns for each day- early and late shift). There will be no rows at start (One row represents one worker). The worker will only be shown only on the tables that match his license line (Worker's Array License Line).
Operation
- Program will create Entity <Timetable>.
- On Entity <Timetable>, it will create <days> <Day> (<days> came from user input previously). Each <Day> will also assign on its constructor the attribute <Day>.<Day Number> which will be passed as a parameter (parameter will be a counter that gets increased within the timetable constructor).
- On each entity <Day> created, it will create <lines> <Line> (<lines> came from input previously).
- Each line on its constructor will have attributes <Line>.<activeday>,<Line>.<activenight> (both boolean values) as false. Why do I have those? Oh, well, it is unreliable to say if the worker is active on day or night on attributes <Line>.<workerDayShift> and <Line>.<workerNightShift>. We can validate them whether they are empty or not. However, what if in the future we want to use those variables and put some meaning to them when it is displayed on our program. For instance, instead of saying nothing, it can say a word, such as "unreserved". In that case, we will have to change the code in our program. In order to avoid that, I added those 2 boolean variables.
Menu
- CreateWorker
- Set Work For A Worker
Worker's user code? Input variable <worker>
Operation
- Go to the menu and loop through all worker's user name and try to find a match with input variable <worker>. If no match, continue. If match, warn user that user name already exists.
- Get the count of days from the Entity <TimeTable>. Do a loop based on the number of days with the following question:
Set the worker's Ability for Day X? Input variable array <WorkerAbility>
End Loop
How many licenses the worker has? Input variable <LicenseLoop>
Start Loop in the length of variable <LicenseLoop>
Pick a License from the list bellow for worker <worker>:
(Show List of Lines the worker does not still have) Input variable array <Licenses>
End Loop
Operation
- Menu will create a new <Worker> entity.
- In its constructor it will pass the input variable array <Licenses> to be assigned to attribute <Worker>.<License Line>.
- In its constructor, We will pass the input variable <worker> to be assigned to attribute <Worker>.<username>.
- In its constructor, we will create X number of <ScheduleDay> (where X represents the input <WorkerAbility>.Length()).
- For each <ScheduleDay>, we assign the attribute <ScheduleDay>.<workerability> based on the input <WorkerAbility> array, <ScheduleDay>.<active> as false (=which represents whether the worker really works or not on that day or not), <ScheduleDay>.<daynumber> which will be passed as a parameter (parameter will be a counter that gets increased within the Worker constructor).
Worker created
Menu
- Create Worker
- Set Work For A Worker
- Shows a list of available workers. User can pick one of the workers.
- Shows a list of Days. User can pick one of the days. (List of days shown will be only the ones where Worker's Schedule Day attribute Active is false AND Worker's Schedule Day attribute Ability is NOT 'A' (Absent) )
- Shows a list of Lines. User can pick a line. (List of lines shown will be only the ones in the Worker's Attribute LicenseLine array)
- What Shift? Input Day or Night (Based on the user input of Day, pick the correct Entity <Day> that contains the DayNumber. Do the same for picking the correct Line entity within that <Day> entity (based on user input, to match with <Line>.<LineNumber>). If user chose "Day", and <Line>.<activeday> is true, then tell user which worker already uses that shift. If user chose "Night", and <Line>.<activenight> is true, then tell user which worker already uses that shift. If not and all is fine, continue and set that <Line>.<active(day/night)> to true and the worker's user name on attribute <Line>.<worker(day/night)shift>.
- Find the correct Worker's Schedule Day based on user input worker and day. Run the function assign(line,shift) to set the worker's schedule day line and shift attributes (parameters come from user input line and shift).