/* Office scheduling problem in Picat. From Minh Vinh Nguyen Phuoc Bao "The Office Scheduling Problem" (https://easychair.org/publications/preprint/7krz) """ Abstract The Coronavirus Disease 2019 has disrupted many aspects of our daily life, such as going to work. To cope with this rapid changes, offices are required to make a more flexible schedule. In this paper, we introduce an approach to this problem using constraint programming. --- The Office scheduling problem takes into account a group of staff who are required to work for a number of hours. Moreover, their tasks are independent, i.e., they do not need to wait for another staff member to finish his/her work. Because every staff member may need to stay home with a child due to school and childcare closures or other reasons, they will be assigned a time slot that fits their own schedule. For the sake of simplicity, let us assume that only one person is allowed to be physically in the office at a time. ... [O]ur objectives are • to determine a working schedule that fits every staff preferences, • and more importantly, to determine an optimal working schedule, i.e., the hour that the office can close the earliest. """ """ 4 Variants of the Office scheduling problem 4.1 Priority working Recall that staff members are equal and work individually. Here, the problem is expanded such that some staff work dependent on others. For example, Alice may have to wait until Bob finishes his work. [hakank: I'm not sure I understand this. Does it mean that Alice have to wait after any work by Bob, or just some specific work at a specific time/order? Or perhaps that Alice have to wait until Bob have finished all his work? The latter interpretation seems more reasonable. Another way to think about this is that the works are idenfified in some way which then makes it possible to say that Alice work #1 must be after Bob's work #2, etc. ] ... 4.2 "New normality” Another variant to this problem can be that it is not limited to just one person in the office at a certain time. For example, there is no restriction for the people who have been vaccinated, while the ones who have not, still have to work separately. [hakank: I added this as an option: Vaccinated is a list of 0/1 where 1 indicates that a person is vaccinated. ] 4.3 Office hour restriction Recall that our Office scheduling problem is fixed between time 1–24. In pratice, offices open from 8A.M. to 5P.M., so everything needs to be finalized between that time. Therefore, two variables need to be input that expresses the starting and ending time. [hakank: This can be fixed easily by restricting the values in the Y array. But for the given availabilites there is no solution. ] """ Some other extensions: - the objective is (also) to get the number of worked hours as simular as possible. This is a multi-objective problem. Here are some tests: * go/0: For the standard problem without any vaccination information there are 8 optimal solutions with z=14. Here is one of them: z = 14 y = {0,1,1,1,1,1,1,1,1,1,1,0,1,1,0,0,0,0,0,0,0,0,0,0} Time: 1 Worker: - Time: 2 Worker: eve Time: 3 Worker: david Time: 4 Worker: alice Time: 5 Worker: david Time: 6 Worker: bob Time: 7 Worker: eve Time: 8 Worker: charlie Time: 9 Worker: bob Time: 10 Worker: eve Time: 11 Worker: eve Time: 12 Worker: - Time: 13 Worker: alice Time: 14 Worker: bob Time: 15 Worker: - Time: 16 Worker: - Time: 17 Worker: - Time: 18 Worker: - Time: 19 Worker: - Time: 20 Worker: - Time: 21 Worker: - Time: 22 Worker: - Time: 23 Worker: - Time: 24 Worker: - * go2/0: Some are vaccinated. With just alice, bob, and charlie as vaccinated it's the same closing time (after 14) with 20 optimal solutions: vaccinated = [alice,bob,charlie] z = 14 y = {0,1,1,1,1,1,1,0,1,1,1,0,1,2,0,0,0,0,0,0,0,0,0,0} Time: 1 Worker: [] Time: 2 Worker: [eve] Time: 3 Worker: [david] Time: 4 Worker: [alice] Time: 5 Worker: [david] Time: 6 Worker: [bob] Time: 7 Worker: [eve] Time: 8 Worker: [] Time: 9 Worker: [bob] Time: 10 Worker: [eve] Time: 11 Worker: [eve] Time: 12 Worker: [] Time: 13 Worker: [alice] Time: 14 Worker: [bob,charlie] Time: 15 Worker: [] Time: 16 Worker: [] Time: 17 Worker: [] Time: 18 Worker: [] Time: 19 Worker: [] Time: 20 Worker: [] Time: 21 Worker: [] Time: 22 Worker: [] Time: 23 Worker: [] Time: 24 Worker: [] * go3/0: All are vaccinated. If they are all vaccinated then they can close at after 13, but not before that. There are 900 optimal solution, for example: vaccinated = [alice,bob,charlie,david,eve] y = {0,0,0,1,0,2,2,0,1,2,1,0,3,0,0,0,0,0,0,0,0,0,0,0} Time: 1 Worker: [] Time: 2 Worker: [] Time: 3 Worker: [] Time: 4 Worker: [alice] Time: 5 Worker: [] Time: 6 Worker: [bob,david] Time: 7 Worker: [david,eve] Time: 8 Worker: [] Time: 9 Worker: [bob] Time: 10 Worker: [bob,eve] Time: 11 Worker: [eve] Time: 12 Worker: [] Time: 13 Worker: [alice,charlie,eve] Time: 14 Worker: [] Time: 15 Worker: [] Time: 16 Worker: [] Time: 17 Worker: [] Time: 18 Worker: [] Time: 19 Worker: [] Time: 20 Worker: [] Time: 21 Worker: [] Time: 22 Worker: [] Time: 23 Worker: [] Time: 24 Worker: [] This model was created by Hakan Kjellerstrand, hakank@gmail.com See also my Picat page: http://www.hakank.org/picat/ */ import cp. main => go. % % Problem 1: No vaccination info. % go ?=> run_problem(1), nl. go => true. % % Problem 2: some of the people vaccinated. % go2 ?=> run_problem(2), nl. go2 => true. % % Problem 3: All are vaccinated. % go3 ?=> run_problem(3), nl. go3 => true. run_problem(Problem) => problem(Problem,People,Available,NumHoursToWork,Vaccinated), NumPeople = People.len, NumTimes = Available.len, println([numTimes=NumTimes,numPeople=NumPeople,vaccinated=Vaccinated]), % Find optimal solution office_scheduling(People,Available,NumHoursToWork,Vaccinated, _X,_Y,Z), println(opt=Z), printf("Find all optimal solutions with Z=%d\n", Z), office_scheduling(People,Available,NumHoursToWork,Vaccinated, X2,Y2,Z), print_solution(People,Available,NumHoursToWork,Vaccinated, X2,Y2,Z), fail, nl. print_solution(People,Available,NumHoursToWork,Vaccinated,X,Y,Z) => NumPeople = People.len, NumTimes = Available.len, UseVaccinated = cond(Vaccinated.len == NumPeople,true,false), println([numTimes=NumTimes,numPeople=NumPeople]), if UseVaccinated then println(vaccinated=[People[P] : P in 1..NumPeople, Vaccinated[P] == 1]) end, office_scheduling(People,Available,NumHoursToWork,Vaccinated, X,Y,Z), println(z=Z), println(y=Y), foreach(T in 1..NumTimes) Worker = [], if Y[T] > 0 then foreach(P in 1..NumPeople) if X[T,P] == 1 then Worker := Worker ++ [People[P]] end end end, printf("Time: %d Worker: %w\n", T, Worker) end, nl. office_scheduling(People,Available,NumHoursToWork,Vaccinated, X,Y,Z) => println(checkZ=Z), NumPeople = People.len, NumTimes = Available.len, UseVaccinated = cond(Vaccinated.len == NumPeople,true,false), X = new_array(NumTimes,NumPeople), X :: 0..1, % Number of people working this hour Y = new_array(NumTimes), if UseVaccinated then Y :: 0..NumPeople else % If none are vaccinated (or no vaccination information) % then they must be alone in the office. Y :: 0..1 end, % A person can only work when available foreach(T in 1..NumTimes,P in 1..NumPeople) Available[T,P] #= 0 #=> X[T,P] #= 0 end, % Number of workers per hour foreach(T in 1..NumTimes) Y[T] #= sum([X[T,P] : P in 1..NumPeople]) end, if UseVaccinated then % If two people works at the same time they must be vaccinated. foreach(T in 1..NumTimes) (Y[T] #> 1) #=> (Y[T] #= sum([X[T,P]*Vaccinated[P] : P in 1..NumPeople])) end end, % Ensure that a person works exactly the stated number of hours foreach(P in 1..NumPeople) sum([X[T,P] : T in 1..NumTimes]) #= NumHoursToWork[P] end, % Extension: work hours are from 8..17. % Note: But this don't get a solution with the other % constraints and the availabilities. % foreach(T in 1..7 ++ 18..24) % Y[T] #= 0 % end, % However, starting at 8 would give some result: closing after time 23 % foreach(T in 1..7) % Y[T] #= 0 % end, % Experiment: Priority working % Person 1 must way until Person 2 finish all his work. % Nope: There is no combination of P1 and P2 that satisfy this % constraint. % member(P1,1..NumPeople), % member(P2,1..NumPeople), % P1 != P2, % println([p1=P1,p2=P2]), % LastP1 #= max([T*(X[T,P1] #= 1) : T in 1..NumTimes] ), % Last work hour for P1 % min_except_0($[T*(X[T,P2] #=1 ) : T in 1..NumTimes],FirstP2), % FirstP2 #> LastP1, % Experiment: Priority working, version 2: % First job of Bob must be after first job of Alice. % This works with the existing availabilities. % % Alice = 1, Bob = 2, % min_except_0($[T*(X[T,Alice] #=1 ) : T in 1..NumTimes],FirstP1), % min_except_0($[T*(X[T,Bob] #=1 ) : T in 1..NumTimes],FirstP2), % FirstP2 #> FirstP1, % The objective is to close the office as soon as possible Z #= max([T*(Y[T] #> 0) : T in 1..NumTimes]), Vars = X.vars ++ Y, % ++ {FirstP1,FirstP2}, if var(Z) then solve($[min(Z),degree,updown],Vars) else solve($[degree,updown],Vars) end. % % Times: 1..12 am,pm -> 0..23 % % % No information about vaccination % problem(1,People,Available,NumHoursToWork,Vaccinated) => Vaccinated = [], problem(2,People,Available,NumHoursToWork,_). % % With some people vaccinated. % problem(2,People,Available,NumHoursToWork,Vaccinated) => People = [alice,bob,charlie,david,eve], NumHoursToWork = [2,3,1,2,4], Vaccinated = [1,1,1,0,0], % Vaccinated = [1,1,1,1,1], % Note that this is in a weird representation: % The times are 1,13,2,14,3,15,4,16,5,17,6,18,7,19,8,20,9,21,10,22,11,23,12,24 % Available = [% a b c d e % % % ampm % [0,1, 0,0, 0,1, 1,0, 0,1], % Time 1 % [0,0, 0,1, 0,1, 0,0, 1,1], % Time 2 % [0,0, 0,1, 0,0, 1,0, 0,1], % Time 3 % [1,0, 0,0, 0,0, 1,0, 1,0], % Time 4 % [0,0, 0,0, 1,0, 1,0, 0,0], % Time 5 % [0,0, 1,0, 0,0, 1,0, 0,1], % Time 6 % [0,1, 0,0, 0,0, 1,1, 1,0], % Time 7 % [0,0, 0,0, 1,0, 0,0, 0,0], % Time 8 % [0,1, 1,1, 0,1, 0,0, 0,1], % Time 9 % [0,1, 1,0, 1,1, 0,0, 1,0], % Time 10 % [0,0, 0,0, 0,1, 0,1, 1,0], % Time 11 % [0,0, 0,0, 0,0, 0,0, 0,0] % Time 12 % ]. % I'll rearrange it as a normal 0..23 clock Available = [% a b c d e % % ampm [0, 0, 0, 1, 0], % Time 0 [0, 0, 0, 0, 1], % Time 1 [0, 0, 0, 1, 0], % Time 2 [1, 0, 0, 1, 1], % Time 3 [0, 0, 1, 1, 0], % Time 4 [0, 1, 0, 1, 0], % Time 5 [0, 0, 0, 1, 1], % Time 6 [0, 0, 1, 0, 0], % Time 7 [0, 1, 0, 0, 0], % Time 8 [0, 1, 1, 0, 1], % Time 9 [0, 0, 0, 0, 1], % Time 10 [0, 0, 0, 0, 0], % Time 11 [1, 0, 1, 0, 1], % Time 12 [0, 1, 1, 0, 1], % Time 13 [0, 1, 0, 0, 1], % Time 14 [0, 0, 0, 0, 0], % Time 15 [0, 0, 0, 0, 0], % Time 16 [0, 0, 0, 0, 1], % Time 17 [1, 0, 0, 1, 0], % Time 18 [0, 0, 0, 0, 0], % Time 19 [1, 1, 1, 0, 1], % Time 20 [1, 0, 1, 0, 0], % Time 21 [0, 0, 1, 1, 0], % Time 22 [0, 0, 0, 0, 0] % Time 23 ]. problem(3,People,Available,NumHoursToWork,Vaccinated) => Vaccinated = [1,1,1,1,1], problem(2,People,Available,NumHoursToWork,_). % % Ensure that the minumum value (> 0) is MinVal. % This requires that there are at least one value > 0. min_except_0(X,MinVal) => Len = X.length, between(1,Len,I), MinVal #= X[I], foreach(J in 1..Len) MinVal #=< X[J] #\/ X[J] #= 0 end, MinVal #> 0.