This article has participated in the activity of “New person creation Ceremony”, and started the road of digging gold creation together.
background
Last weekend I met my girlfriend on the schedule, spent almost an hour, so I thought I could save her some time by looking at the code.
The problem research
I looked it up online, read some papers and got the background.
Citeseerx.ist.psu.edu/viewdoc/dow…
Arxiv.org/pdf/1804.05…
It is a Nurse Rostering Problem. It is nP-hard in terms of complexity
P problems are problems that can be solved in polynomial time, while NP problems are problems that can be verified in polynomial time
What does polynomial time mean? I understand it is the algorithm complexity of ordinary calculation
Dsmic-time O(N) -LINEAR time O(N ^2) -QUADRATIC time O(N ^k) -polynomial-time O ^ n (k) - an exponential - time O (n!) - the factorial - timeCopy the codeA description of NP problems can be found in this article I found
Complexity theory is mentioned because the right tool can be found only after the problem is analyzed more accurately.
We will think of using computer science methods to deal with such problems, such as Machine learning.
Tool finder – Find the shoulders of giants
Machine learning stack. I learned scikit-learn, TensorFlow and Keras in Python to make choices
As far as I know, this is a subject that has been studied for many years. In that case, there should be ready-made models trained to do this sort of thing.
Finally, I found or-Tools (Official Site) developed by Google. It already has models trained to deal with such scheduling problems.
Action
Code example
Official example Source Code
The main is to make adjustments to the source code to meet real needs.
Or-tools basic usage
Pseudocode excerpted to understand how it works
// Select and define a model, then set the required pre-data and constraints model = cp_model.cpModel () model.newBoolvar (...) model.AddExactlyOne(...) model.Add(...) // Select and define a solver, Solver = cp_model.cpsolver () status = solver.solve (model, // create a matrix for work = {}for e in range(num_employees):
for s in range(num_shifts):
for d in range(num_days):
work[e, s, d] = model.NewBoolVar('work%i_%i_%i'% (e, s, d)) // Here is the algorithm for printing the resultif status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
print()
header = ' '
for w in range(num_weeks):
header += 'M T W T F S S '
print(header)
for e in range(num_employees):
schedule = ' '
for d in range(num_days):
for s in range(num_shifts):
ifWork [e, S, D]): // NOTE: Shifts [S] +' '
print('worker %i: %s' % (e, schedule))
print(a)Copy the codeParameter adjustment
The parameter comments in the sample source code are clearly marked for use, and should be adjusted to suit the needs of real-world problems. The pseudocode below is just a few instructions for the parameters.
num_employees = 4// number of employees, change to number of target employees num_weeks =5// The number of working days is set to one month5Weeks shifts = ['O'.'M'.'A'.'N'[// Schedule, same as goal# Fixed assignment: (employee, shift, day).
# Fixed for the first two days, dynamic adjustment should be made before scheduling
fixed_assignments = [
(0.0.0),
(1.1.0),
(2.2.0),
(3.3.0),
(0.0.1),
(1.1.1),
(2.2.1),
(3.3.1),]# Request: (employee, shift, day, weight)
# Employees want to fix the rest time (position), and the weight value I understand represents the priority that can be adjusted when fitting
requests = [
# Employee 3 does not want to work on the first Saturday (negative weight for the Off shift).
(3.0.5, -2),
# Employee 2 does not want a night shift on the first Friday (positive weight).
(2.3.4.4)]# Shift constraints on continuous sequence :
# (shift, hard_min, soft_min, min_penalty,
# soft_max, hard_max, max_penalty)
# HARD_min: hard limit, the minimum number of consecutive days to work in a cycle
# soft_min: soft limit, minimum number of consecutive days to work in a cycle
# soft_max = hard_max
shift_constraints = [
# One or two consecutive days of rest, this is a hard constraint.
(0.1.1.0.2.2.0),
# betweem 2 and 3 consecutive days of night shifts, 1 and 4 are
# possible but penalized.
(3.1.2.20.3.4.5),]# Weekly sum constraints on shifts days:
# (shift, hard_min, soft_min, min_penalty,
# soft_max, hard_max, max_penalty)
weekly_sum_constraints = [
# Minimum number of days off per week
(0.1.2.7.2.3.4),]# Penalized transitions:
# (previous_shift, next_shift, penalty (0 means forbidden))
penalized_transitions = [
# Try to avoid switching from afternoon to evening shifts
(2.3.4),
The evening shift cannot be followed by the morning shift
(3.1.0),]# daily demands for work shifts (morning, afternon, night) for each day
# of the week starting on Monday.
# How many people should there be at least in each class? The practical problem here is that only one person is enough
weekly_cover_demands = [
(1.1.1), # Monday
(1.1.1), # Tuesday
(1.1.1), # Wednesday
(1.1.1), # Thursday
(1.1.1), # Friday
(1.1.1), # Saturday
(1.1.1), # Sunday
]
# Penalty for exceeding the cover constraint per shift type.
excess_cover_penalties = (2.2.5)
num_days = num_weeks * 7
num_shifts = len(shifts)
Copy the codeDraw a gantt chart
In the technical stack, matplot is selected to draw gantt charts, also learn now sell now.
# Generate plot image. [reference: https://www.geeksforgeeks.org/python-basic-gantt-chart-using-matplotlib]
shifts_colors = ['white'.'tab:green'.'tab:orange'.'tab:blue']
if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
offset = 2
# Declaring a figure "gnt"
fig, gnt = plt.subplots()
# Setting Y-axis limits
gnt.set_ylim(0, num_employees * 15)
# Setting X-axis limits
gnt.set_xlim(1, num_days + offset)
# Setting labels for x-axis and y-axis
gnt.set_xlabel('Dates')
gnt.set_ylabel('Employees')
# Setting ticks on y-axis
# gnt.set_yticks([15, 25, 35, 45])
gnt.set_xticks(list(range(1, num_days + offset, 1)))
gnt.set_yticks(list(range(15, (num_employees + 1) * 10 + 5.10)))
# Labelling tickes of y-axis
gnt.set_yticklabels(employees_names)
# Setting graph attribute
gnt.grid(True)
for e in range(num_employees):
for d in range(num_days):
for s in range(num_shifts):
if solver.BooleanValue(work[e, s, d]):
gnt.broken_barh([(d+1, d+2)], (10*(e+1), 9),
facecolors=(shifts_colors[s]))
plt.savefig("gantt1.png")
Copy the codeResults:
conclusion
- A good understanding of the problem will help you find the tool
- Fortunately, there has been research on this topic. Only by studying the topics I have studied and being familiar with tools and solutions can I better solve other problems
Combat code: github.com/pascallin/N…