There are already several good responses to the DMCommunity’s April-2020 Challenge “Doctor Planning”. Below I am describing how I tried to use this challenge to create a complete decision optimization service. I ended up with a working Worker Scheduler that shows a solution for this particular challenge in Fig. 1 (click to open):
From a Challenge to a Working Service
The Challenge describes a relatively simple scheduling and resource allocation problem:
I know that many smart people using their favorite tools can quickly implement different optimization problems, and this simple challenge only confirms this fact. I also could quickly to solve this problem with JavaSolver, but I had no particular interest in doing so as similar solutions have been already provided. Then I thought that this challenge shows a real problem with many Decision Optimization services in general: researches usually concentrate on the most difficult algorithmic part, but they usually limit themselves to this part only. Why not to provide a complete solution with a friendly data entry, nice displaying of the optimization results? It’s usually done for big (well-funded) projects. But in the modern world, why not to make our decision services commonly available as AWS Lambda or other type of microservices? Then people can actually start using such services.
So, this weekend I decided to implement a working Worker Scheduler that would not be limited to doctors only and to the restrictions of this particular challenge. I wanted to build something practical that can be used by real-world schedulers to solve many similar or much more difficult worker scheduling problems. Today, 3 days later, I’ve completed the first release that I’m not ashamed to share. Now, it’s available from AWS and everybody can try it from http://amazon.openrules.com:8080/DoctorPlanning/
Below I will share how I actually implemented this Worker Scheduler. I split it into two independent parts:
- Scheduling GUI
- Implemented using OpenRules Dialog with all presentation and interaction logic in Excel
- Deployed on AWS EC2 instance
- Scheduling Decision Service
Building Scheduling GUI
I started with the Scheduling GUI that is supposed to give a human scheduler a friendly interface to do everything manually (to start with). When a user decides to do an automatic scheduling, he/she would be able to push the button “Schedule”. However, initially, I didn’t think how to implement this button at all. My logic was that this button will call a remote Scheduling Decision Service that I always could implement later using a JavaSolver or any other generic scheduling tool. Starting with an understanding of WHAT your decision service is supposed to do and not to worry about HOW it works is a good decision modeling practice.
Building a GUI using mainly Excel with predefined OpenRules GUI templates is not difficult at all. So, first I created an initial Weekly Schedule that seems to be intuitive to a human scheduler:
It shows an empty schedule with Days and Shifts in columns and workers (doctors) in rows. Initially, all shift boxes are white (free, not scheduled but available). The a user can select different actions (Assign, Block, or Free) and click on the white boxes to make them “Blue” (manual, frozen assignment) or “Black” (blocked, not available). To imitate a user, I made all cells from Mon to Fri for the doctor Fleming “Black” as he is available only on Fri, Sat, and Sun. Similarly, I blocked unavailable night shifts for doctors Freud and Heimlish. Trying to add night shift constraints I understood that somehow I need to know if a worker was assigned to a night shift on the previous Sun. So, I understood that the schedule should also show the previous Sun to allow a user adding (manually) previous assignments. Now my updated schedule looked as follows:
But how could a user enter the constraint “A worker allows max 2 night shifts”? It is a piece of information that is worker-specific and should be entered in the table that shows all workers. So, I decided to add the button “Settings” that will show a different page where the user would be able to add/delete workers and enter additional information about them. Thus, I added the page “Setting” that looked as follows:
Now a human scheduler is ready to use frozen assignment for manual scheduling while keeping all scheduling constraints in her/his mind.
So, my GUI started to be real and worked fine on my local Tomcat server. Then, I easily deployed it to the AWS EC2 instance with just a simple upload of the automatically generated war-file. Now, I had the first version of the Worker Scheduler available for everybody online. It just provided manual scheduling while the button “Schedule” did nothing. But what was even more important is the fact that now I understood the peculiarities of the problem much better and was ready to start the development of the proper Scheduling Decision Service.
Integrating Scheduling GUI with AWS Lambda Service
But I was not in a hurry to jump in such development. Instead of building a full-scale scheduling decision service, first I decided to concentrate on the integration of the GUI with a remote AWS Lambda. The integration scheme that I wanted to implement is presented the following architectural picture:
This cloud-based architecture allows me to concentrate on my problem and to rely on the cloud framework (such as AWS) taking care about high availability, security, load balancing, multi-tenant support, etc.
To make this scheme to work ASAP, I decided first to create a simple stub that would fill out all available shifts without any constraints, and then deploy this stub-microservice as AWS Lambda. It should allow me to test the integration of already developed GUI and my AWS Lambda function.
My entire GUI implementation was done in one Excel file and two simple Java classes Plan and Doctor. So, I used OpenRules Decision Manager to build a decision service called “DoctorPlanning” with the following functionality:
- Take a request with an object of the type Plan that already contains all doctors and their availability information;
- Make all available shifts for all doctors “scheduled”
- Return a response with the modified object Plan with all modified doctor shifts.
This problem is much easier to compare with many sample problems (e.g. “VacationDaysLambda”) already included into OpenRules Decision Manager. So, I quickly completed this service and with a simple click was able to deploy it as an AWS Lambda. It provided me with the endpoint URL that can be used to invoke this Lambda function remotely.
Then I went back to my Scheduling GUI, and associated with the button “Schedule” a little Java program that utilizes the standard OpenRules class DecisionServiceClient. To do this, I needed to add several additional jar-files to the GUI classpath. Quite In almost no time, I was able to click on my button “Schedule” and it produced a schedule similar to the one in Fig. 3 but with all white (available) cells being green (scheduled).
Now my GUI had not 2 but 3 buttons:
- Schedule – call the remote Scheduling Decision Service
- Reset – to remove all automatically made (green) assignments
- Setting – to provide scheduling.
My GUI was successfully integrated with the remote AWS Lambda service and I could concentrate on the service itself.
Developing Scheduling Decision Service
To convert my simple Java stub to a real scheduling decision service I decided to use JavaSolver and added its dependencies to my pom-file. Here’s where the fun began. The first version was ready within an hour (it is similar to what other submitters like Alex Fleischer report). That’s when I really appreciated all efforts we put in the creation of the OpenRules Decision Manager’s One-Click AWS Lambda deployment mechanism. I was able to test different versions of my service directly from constantly running GUI: without restarting GUI I was able to make changes in my JavaSolver code, deploy it with one click, and test it again! This process helped my to quickly fix several initial errors and misconceptions.
This way, I relatively quickly received a working scheduler. Other submitters have already already complained that scheduler can produce millions of possible solutions and wondered if there are any constraint to chose among them. I faced the same issue. While my first found scheduling solution satisfied all constraints, it didn’t look pretty – the automatically produced shift assignment was very unbalanced. So, first of all I decided to add two more constraints:
- Minimal Workers per Shift (1 as the default)
- Maximal Workers per Shift (2 as the default)
After I added these constraints, a push on the button “Schedule” (without restart!) produced a schedule that looked much more balanced.
Then I asked myself: what if a user will add more workers? Probably, a user should be able to change the thresholds (1 and 2) of these constraints. So, I added the proper parameters to the GUI Settings.
Then I decided to define an optimization objective and instead of one feasible solution ask my service to produce an optimal solution! I specified several optimization objectives and also added them to the Settings page for a user to choose from. Alex Fleischer has already implemented one objective “to spread the workload in order to be as fair as possible.” As my additional min/max constraints already direct the scheduler in the direction of “fairness”, I decided to implement the objective “Maximize Resource Utilization”. To do this, I defined the objective as the difference between available and automatically scheduled shifts for all workers and all days. And then I asked the scheduler to maximize this objective – it required only to change one call solve() to maximize().
When I tested the new version of the scheduler against different combinations of workers, frozen constraints, and minimal/maximal limits for workers per shifts, the produced optimal solutions looked really good. Sometimes, I managed to create situations when no solutions can be found, and the scheduler produced the message: “The Schedule is over-constrained. Scheduling was not successful!” At the same time, a human scheduler should be allowed to override any constraints imposed by the automatic scheduler. So, I made the scheduler more flexible and sometimes instead of failing, it produces a response like this one: “Warning: cannot enforce doctor Golgi to work only one shift on Tue. Scheduling was Successful!”
JavaSolver allows me to switch between different underlying solvers without changing anything in the scheduling code. So, I simply used different dependency in my pom-file for the Scheduling Decision Service. So far, I tried two open-source constraint solvers available from the MVN Repository under the names:
Sugar-based implementation (from Kobe University, Japan) was extremely fast while Constrainer took a lot of time to prove the solution optimality. So, I added one more scheduling parameter “Scheduling Time Limit” with the default 10 seconds. Now both solvers were able to produce good solutions within 10 seconds while Sugar usually managed to produce the optimal solutions. The latest page “Settings” now looks as follows:
Now I want to invite you to try the current implementation of the Worker Scheduler from http://amazon.openrules.com:8080/DoctorPlanning. There is no registration and it’s completely free. The code of the actual solver is available from here “OptimizationProblem.java”. Both Scheduling GUI and Decision Service will be included in the next OpenRules release. I can provide you with all sources upon request.
I understand that this Worker Scheduler can be made much more flexible, e.g. support schedules without shifts, covering several weeks, saving previous results, adding more constraints and optimization objectives, interface with Google Calendar, etc. So, I’d appreciate your suggestions for improvement. At the same time, it seems to me this quickly created Worker Scheduler is already can be used “as is” by small businesses for scheduling of doctors, nurses, dentists, bank tellers, etc. I hope it demonstrates my initial point: to make Decision Optimization more practical, the developers should not limit themselves to the algorithmic parts only.
P.S. If you represent a healthcare-related business that wants to customize this service and/or use a similar service during the coronavirus time, then contact me and I’d glad to allocate my personal time without any compensation to help you to create the proper decision optimization service and put it in the real-world production environment.