Schedule Algorithm for Determining Two-Dimensional Constraints

Question

I was assigned to make a planning program at my company. Basically this employee N you should plan the transition for a month. I tried to do this with brute force and ordered the restriction priority. However, I am having problems trying to maintain vertical and horizontal constraints.

Vertical restrictions, each person should have an equal number of shifts per month. (for example, they should be within the average number of day shifts, night shifts, rest days, early shifts). However, there is also a horizontal day limit when the number of shifts per day should be equal daily.

I tried searching on the Internet and I usually read the answer about using the genetic algorithm. In my study of the Genetic Algorithm, it seems that the algorithm is not suitable for my case. Does anyone know how to solve this problem?

Additional illustration based on Enigmativity comment: There are basically 4 shifts,

Y is the total shift of an employee for a month, which should be evenly distributed among one employee. (i.e., each employee should have an equal (or just a difference by one) magnitude of the type of shift per month) - a vertical constraint.

X is the daily amount for all employees, basically each shift should also be evenly distributed for drawdowns and for the weekend. - horizontal constant

In addition, there are other limitations, such as required shifts and adjacent shifts. But I tried to simplify it with these rules even this time.

-------------------------------------------------------------------------------- | Employee | 1 | 2 | 3 | 4 | + + + | 28 | 29 | 30 | 31 | S1 | S2 | S3 | S4 | -------------------------------------------------------------------------------- | EmpA | S3 | S4 | S1 | S2 | + + + | S3 | S4 | S1 | S2 | Y | Y | Y | Y | -------------------------------------------------------------------------------- | EmpB | S1 | S3 | S4 | S1 | + + + | S2 | S3 | S4 | S1 | Y | Y | Y | Y | -------------------------------------------------------------------------------- | EmpC | S2 | S1 | S3 | S4 | + + + | S1 | S2 | S3 | S4 | Y | Y | Y | Y | -------------------------------------------------------------------------------- | EmpD | S2 | S2 | S2 | S3 | + + + | S4 | S1 | S2 | S3 | Y | Y | Y | Y | -------------------------------------------------------------------------------- | S1 | X | X | X | X | + + + | X | X | X | X | | | | | -------------------------------------------------------------------------------- | S2 | X | X | X | X | + + + | X | X | X | X | | | | | ------------------------------------------------------------------------------- | S3 | X | X | X | X | + + + | X | X | X | X | | | | | -------------------------------------------------------------------------------- | S4 | X | X | X | X | + + + | X | X | X | X | | | | | -------------------------------------------------------------------------------- 

Answer 1

I am currently working on a nursing planning issue that is very similar to yours. The goal is to schedule a shift (or day off) for each nurse every day, so that they work with the correct shifts (40-hour work week) and meet the basic shift requirements per day (3 nurses on Monday, 2 days, etc.) .d.). This is a well-known issue, and like any other schedule issues, it is NP-Hard.

I agree with your comment that genetic algorithms are not suitable for this task (or for any imo task). There are much more effective approaches to solving this problem, and they have been studied and well documented in the areas of programming programming and constraint operations.

My advice would be to take a mathematical programming language to simulate your problem and code it as a constraint programming problem or a mixed integer linear program (MILP). There are several languages ​​that allow you to code these problems at a high level, the most famous of which is likely to be AMPL. You can find an example of nursing planning for this language, which is likely to help many. AMPL can easily be compiled into MILP, which can then be passed to the solver, such as GLPK or CPLEX. In addition, if you work in academia or have a decent enough budget for this problem, you should consider purchasing the IBM ILOG CPLEX package and coding your problem in a supported optimization programming language (OPL). This is the language / solver that I use, and I am very pleased with it.

Keep in mind that this is a difficult problem from an extremely computational point of view, and I would make sure that you are familiar with this difficulty before you make any cost estimates for the project.

Edit: Since you updated your question, let me update my answer, OPL code works here to solve your problem. I will use OPL because I do not know AMPL, but the two languages ​​are very similar, you can easily translate.

 using CPLEX; int nbShifts = ...; int nbDays = ...; int nbEmpl = ...; range sRng = 1..nbShifts; // for indexing range dRng = 1..nbDays; range eRng = 1..nbEmpl; int shiftsWorked[eRng] = ...; // number of shifts each employee works int shiftsRequired[dRng][sRng] = ...; // number of shift s required on day d dvar int Assignments[eRng][dRng][sRng] in 0..1; // boolean matrix, 1=working 0=not working subject to { // work at most 1 shift per day forall(e in eRng, d in dRng) (sum(s in sRng) Assignments[e][d][s]) <= 1; // "vertical" constraint forall(d in dRng, s in sRng) shiftsRequired[d][s] == (sum(e in eRng) Assignments[e][d][s]); // "horizontal" constraint forall(e in eRng) (sum(d in dRng, s in sRng) Assignments[e][d][s]) == shiftsWorked[e]; } // to print out A, in nicer format execute { write("\n"); var flag; for (var e=1; e <= nbEmpl; e++) { for (var d=1; d <= nbDays; d++) { flag=0; for (var s=1; s <= nbShifts; s++) { if (Assignments[e][d][s] == 1) { flag=1; write(" S",s); } if (s == nbShifts && flag==0) write(" __"); } } write("\n"); } } 

You can run this code with a .dat file as follows:

 nbShifts = 4; nbDays = 7; nbEmpl = 4; shiftsWorked = [ 5 5 5 5 ]; shiftsRequired = [[3 0 0 1] [1 1 0 0] [0 0 1 1] [1 1 1 1] [0 0 0 0] [1 0 0 3] [0 2 2 0]]; 

And get the following result in less than a second:

  S1 __ S3 S4 __ S4 S3 S1 __ S4 S3 __ S4 S3 S1 S2 __ S2 __ S4 S2 S4 S1 __ S1 __ S1 S2 

I would like someone to tell me about this when I started my problem;)

Answer 2

Have you looked at the Drools Planner (open source ASL, Java)? There is an example of a nurse filing (= correspondence of employees), very similar to what you are doing, and it is riddled with restrictions.

Answer 3

As follows from the comments, this is a chart for cars - for people, we need more information. In addition, this “genetic algorithm” is too high for this task. You can do this with arrays / objects, iterations, configuration settings, and recursion.

What language do you use?

Answer 4

I wrote a simple algorithm in C # that can solve the schedule problem with 0 conflicts between teachers, rooms and lectures at the same time. His idea is quite simple: 1- Create possible lectures for each teacher (teacher + time period). 2 - generate possible lectures for each room (room + time period). 3- take a random period from this list of teachers and check two things. a - does this random period exist in indoor periods? b is a random period not taken by the same class of students? if these two conditions are true, then you need to do 3 things: 1- select a room with the same period and add it to the solution (in the list of solutions). 2- remove this time period from the lists of teacher periods and time periods. otherwise repeat the process.