+ Reply to Thread
Results 1 to 14 of 14

Complex scheduling problem using SOLVER

  1. #1
    Registered User
    Join Date
    07-31-2014
    Location
    Stockholm, Sweden
    MS-Off Ver
    2013
    Posts
    7

    Complex scheduling problem using SOLVER

    Hi, I'm trying to optimize scheduling of meetings between individual students and individual teachers in one day.

    To simplify the problem, I have the following information and constraints:

    - Nr of students: 10
    - Nr of teachers: 5
    - Nr of available timeslots: 10
    - Each student must choose 4 teachers to meet in order of preference (1-4) but will only be allocated exactly 3 meetings.
    - Only one student and one teacher per meeting
    - A student can meet a teacher only once
    - A teacher can do one meeting per time slot
    - Some students are not available in all time slots

    See the attachment for how I have tried to approach the problem.



    Grateful for any advice how I can solve this as I'm not so experienced using solver. Thanks
    Attached Files Attached Files
    Last edited by D4rwin; 02-05-2021 at 03:45 PM.

  2. #2
    Valued Forum Contributor Hydraulics's Avatar
    Join Date
    07-15-2018
    Location
    Udine - Italy
    MS-Off Ver
    Office 365
    Posts
    369

    Re: Complex scheduling problem using SOLVER

    Your problem is rather complex, indeed. It can be solved with Excel, but you need to install OpenSolver, a free Add-In that has no limits on the number of variables and constraints.

    Translating the constraints in linear equations, and without using logical and reference functions, is somewhat tedious. If you plan to use the worksheet regularly, I would explore the possibility to add some VBA code.

    There are 500 binary variables: 5 teachers * 10 timeslots * 10 students. I have added colors to help you identify the new equations, and added some name ranges that will show up in the OpenSolver mask.

    The objective function to maximize is total timeslots value (so that meetings end as soon as possible), with the added constraint on student preference order.

    Solution time is < half a second on my PC.

    If I find something easier I'll post an update.

    HTH,

    Francesco
    Attached Files Attached Files
    Last edited by Hydraulics; 01-31-2021 at 09:15 AM.
    Aim high or don't even try.
    ---------------------------------
    If your question has been answered, don't forget to mark the thread as SOLVED.
    If you find an answer helpful, click on the star icon at the bottom of the post.

  3. #3
    Registered User
    Join Date
    07-31-2014
    Location
    Stockholm, Sweden
    MS-Off Ver
    2013
    Posts
    7

    Re: Complex scheduling problem using SOLVER

    Hydraulics - thank you so much, an incredible solution.

    The reality is that I have 200 students and 50 teachers and 21 timeslots (=210,000 variables), so I may very well need to code something to simplify the process.

    Having looked through your solution, the only part I don't fully grasp is the 'order of preference constraint'. Did you go through each student choice and write the formula manually?

    Thanks!

  4. #4
    Valued Forum Contributor Hydraulics's Avatar
    Join Date
    07-15-2018
    Location
    Udine - Italy
    MS-Off Ver
    Office 365
    Posts
    369

    Re: Complex scheduling problem using SOLVER

    Scheduling problems can sometimes be solved using Integer (binary) Programming, and Solver/OpenSolver, but there exist other approaches.
    In your problem there is, in my view, a true Objective Function that can be maximized, therefore IP may be a viable method.

    You are right, the order of preference and the values for the OF are the "tedious" part, and where I would suggest a VBA approach.
    OpenSolver will not work with reference functions, but once you know the student preference matrix and have chosen a setup, you can run a small macro to write on the worksheet the formulas that are now in rows 49-58.

    In cell C49, for instance, there is a SUMPRODUCT with a fixed term (the row with the timeslots), and a variable one.
    You can find starting and ending column for each teacher with the aid of a matrix, as you can see in the attached worksheet. Then you need some INDEX/MATCH to get the right boundaries for each student (row) and best teacher (column).

    Since there are 210K bin vars, you may want to set a Branch and Bound tolerance (found under Model/Options...) rather high at the start, say 10%.

    HTH,

    Francesco
    Attached Files Attached Files

  5. #5
    Registered User
    Join Date
    07-31-2014
    Location
    Stockholm, Sweden
    MS-Off Ver
    2013
    Posts
    7

    Re: Complex scheduling problem using SOLVER

    Looking at the constraints you defined I believe it can be simplified as the order of the meetings does not matter. Instead, what matters is that each students gets as many of their preferred meetings as possible, as ranked by 1 (highest) to 4 (lowest).

    As such, I believe the OF needs to minimize the sum of the corresponding ranked meeting values.
    I've tried setting the constraint that the sum of the 3 meeting values must be at least 6 (1+2+3), but the problem is that the solver sometimes chooses only two meetings with values 2 and 4 (=6).

    How can I define a constraint such that the SUM of the meeting values per student must be >=6 AND count of meeting values must be =3.

    (Nice to have but not critical: In some cases the students choose less than 3 meetings so, ideally, the solver would only allocate the nr of meetings chosen, but max 3).

    Thanks!
    Attached Files Attached Files

  6. #6
    Valued Forum Contributor Hydraulics's Avatar
    Join Date
    07-15-2018
    Location
    Udine - Italy
    MS-Off Ver
    Office 365
    Posts
    369

    Re: Complex scheduling problem using SOLVER

    Quote Originally Posted by D4rwin View Post
    Looking at the constraints you defined I believe it can be simplified as the order of the meetings does not matter. Instead, what matters is that each students gets as many of their preferred meetings as possible, as ranked by 1 (highest) to 4 (lowest).
    Then you can simply remove the order constraints I set up in my first worksheet (1st choice <= 2nd choice and 2nd choice <= 3rd choice).

    We still want to maximize the same OF and end meetings as soon as possible (that is, assuming this is your aim. If I were a teacher, I would gladly go home one hour sooner, if I could! Actually, without order constraints, all meetings are satisfied in 7 timeslots instead of 9.)

    (Nice to have but not critical: In some cases the students choose less than 3 meetings so, ideally, the solver would only allocate the nr of meetings chosen, but max 3).
    This is a bit trickier. One way to approach it, is setting a zero in the student preference matrix if there are less then 3 choices, and then multiply the OF by the logical value (automatically converted to 1 or 0) found in each cell.
    The conditional formatting rule has been updated (and a helper column added) to reflect changes, in order to show only two choices when needed.

    HTH,

    Francesco
    Attached Files Attached Files
    Last edited by Hydraulics; 02-02-2021 at 06:08 PM.

  7. #7
    Registered User
    Join Date
    07-31-2014
    Location
    Stockholm, Sweden
    MS-Off Ver
    2013
    Posts
    7

    Re: Complex scheduling problem using SOLVER

    This is incredibly helpful. You're a genius

    One issue though is that the 4th choice of each student doesn't seem to be considered in the equation at all.
    The 4th choice is effectively a back-up choice in case the first three choices are not possible to schedule due to conflict.

    Perhaps I'm just not understand the mechanics well enough.

    Thanks.

  8. #8
    Valued Forum Contributor Hydraulics's Avatar
    Join Date
    07-15-2018
    Location
    Udine - Italy
    MS-Off Ver
    Office 365
    Posts
    369

    Re: Complex scheduling problem using SOLVER

    Quote Originally Posted by D4rwin View Post
    You're a genius
    Well, thank you, but I think you are somewhat exaggerating.

    As for the 4th choice, you are right, I haven't added it to the model. However, we can still use the same framework: the equations for the OF are the same used in the 3rd column, but this time we multiply the value by 0.05.
    Since the algorithm behind Solver looks for the combination that maximizes our function, the 4th choice that adds at most 0.5 will be used only if the problem is infeasible considering only the first three choices.

    To test the model, I had to set the same choice order for every student, and also add again the constraint on the first preference order. As you can see in the attached file, 2 students are thus forced to meet with teacher 4.
    Since in reality the order of the meetings doesn't matter, I take it that teacher 4 being in first position for student 8 wouldn't be a problem.
    Please note I have changed the global constraint on the sum of meetings for each student, linking it to the helper column at the top.

    If you plan to extend the model, be warned that you should keep all variables together, since there is a limit on the number of chars the parser can digest. The union of 50 different ranges will surely exceed it.
    The green constraints then would need to be built with some VBA code.

    HTH,

    Francesco
    Attached Files Attached Files
    Last edited by Hydraulics; 02-02-2021 at 06:05 PM.

  9. #9
    Registered User
    Join Date
    07-31-2014
    Location
    Stockholm, Sweden
    MS-Off Ver
    2013
    Posts
    7

    Re: Complex scheduling problem using SOLVER

    Thank you for this elegant solution Francesco, much appreciated.

    Is there a reason you specifically chose 0.05 and not, say, 0.5?
    If I wanted to add additional optional meeting choices (option 5, 6, etc) I suppose I would do the same and multiply each one a value successively lower than 0.05?

  10. #10
    Valued Forum Contributor Hydraulics's Avatar
    Join Date
    07-15-2018
    Location
    Udine - Italy
    MS-Off Ver
    Office 365
    Posts
    369

    Re: Complex scheduling problem using SOLVER

    Quote Originally Posted by D4rwin View Post
    Is there a reason you specifically chose 0.05 and not, say, 0.5?
    The fourth option must be chosen only when the problem cannot be solved with the first three alone. This implies that its maximum value should always be smaller than the minimum calculated with the formula that assigns a value to a timeslot.
    For instance, with 10 timeslots, the minimum is 1. If we introduce a 4th option, we want to be sure that its value will always be < 1, no matter which timeslot is chosen (because order preference doesn't matter, and the algorithm will always try to find the highest value).
    Setting a value of 0.05, its value can never be > 0.5, therefore we are assured the 4th teacher will never be chosen, unless the model is infeasible scheduling only the first three.

    If I wanted to add additional optional meeting choices (option 5, 6, etc) I suppose I would do the same and multiply each one a value successively lower than 0.05?
    Yes, if you have more options, you can follow the same reasoning: nth option value should never be higher than (n-1)th option, no matter what timeslot we choose.
    However, I wonder if you really need more backup options.
    I have tested the model with 50 teachers, 200 students and 21 timeslots with random values (some formulas have been deleted to get a worksheet smaller than 1 MB). I had to build 2 macros, one for the green constraints (must be run only the first time you setup the model), and one for the objective function, that should be run everytime input data are changed.
    Solution time is less than 30 seconds (not too shabby for a model with 210k vars!), but setup time is more or less 40 minutes. This is due to the interaction of OpenSolver with Excel, and cannot be reduced.
    A possible workaround would involve using SolverStudio and Python/Pyomo.

    HTH,

    Francesco
    Attached Files Attached Files

  11. #11
    Registered User
    Join Date
    07-31-2014
    Location
    Stockholm, Sweden
    MS-Off Ver
    2013
    Posts
    7

    Re: Complex scheduling problem using SOLVER

    This looks perfect.
    When I apply the full set of time constraints, I notice that in a few instances students do not get their first choice meeting. I wonder if there is a quick way to set a constraint that they must at least get their first choice meeting.

    Thanks

  12. #12
    Valued Forum Contributor Hydraulics's Avatar
    Join Date
    07-15-2018
    Location
    Udine - Italy
    MS-Off Ver
    Office 365
    Posts
    369

    Re: Complex scheduling problem using SOLVER

    Quote Originally Posted by D4rwin View Post
    This looks perfect.
    But it isn't, actually.

    I suppose there are many forbidden timeslots (upper right matrix), or maybe preferences are very skewed towards some teacher? Could you upload an anonymized worksheet with your true input data?

    Preference order should be added again as a constraint, at least for the first two meetings, and it can be done solely with some VBA code, but I have this eerie feeling it may cost a lot in terms of solving time.
    I would like to make some test and adjust parameters, if needed, before attaching the (real) perfect working solution.

    HTH,

    Francesco

  13. #13
    Registered User
    Join Date
    07-31-2014
    Location
    Stockholm, Sweden
    MS-Off Ver
    2013
    Posts
    7

    Re: Complex scheduling problem using SOLVER

    In order to reduce the size of the workbook I've had to cut the number of students and teachers down from 100 each.
    As you can see, I've added a few more pieces of information and modified some constraints as follows:

    1. Teacher availability matrix - populates 'teach_avail' below the variable input
    2. 'must_meet' - to ensure that the first choice is allocated, used as constraint against 'one_meet'
    3. The number of meetings per student must be at most 8
    4. The order does not matter
    5. They must meet with their FIRST choice. The remaining 7 meetings to schedule can be selected from any of the remaining choices, and in any order.

    It's a total monstrosity of a model. I've tried to run it a few times but after 3 hours I had to stop it because it was taking too long.
    Attached Files Attached Files

  14. #14
    Valued Forum Contributor Hydraulics's Avatar
    Join Date
    07-15-2018
    Location
    Udine - Italy
    MS-Off Ver
    Office 365
    Posts
    369

    Re: Complex scheduling problem using SOLVER

    The objective function must expressly include the variables of your problem. Think about it as a very long equation, where in each term we multiply a variable (that we must set to 0 or 1) by a timeslot value.
    If you copy the values of these terms, OpenSolver will happily build all the equations with the constraints, and then find that you are not really asking to maximize or minimize anything, because the OF has no variables in it.
    This is still a valid model, and the solution will satisfy (if possible, of course) all the constraints.
    My macro, instead, copied the formulas in the right cells, because in order to build them, I should have used lookup functions, or spent a couple of days selecting manually all the ranges.
    I have adapted it to your setup, I hope the comments are clear enough to let you modify it.

    We can force OS to satisfy the first choice with the same trick used for backup options: we multiply the value of the OF by 25.
    Please note that this will NOT guarantee every student gets its first choice: if a teacher has more first preferences than available timeslots, someone will have to give in.
    The OF for preferences 9 and 10 has been updated.

    Building time is more or less the same. If your original worksheet has 100 students and 100 teachers, I guess it may take a couple of hours, or even more, in order to set up the complete model. The smaller the number of choices, the faster the building.
    Solving time, however, is still pretty nice (much less than 30 secs with a tolerance of 1%).

    Let me know if this solution works for you.

    HTH,

    Francesco
    Attached Files Attached Files
    Last edited by Hydraulics; 02-09-2021 at 08:36 AM.

+ Reply to Thread

Thread Information

Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)

Similar Threads

  1. Replies: 8
    Last Post: 12-30-2020, 04:12 AM
  2. [SOLVED] Staff scheduling with maximum free WE - to be calculated by Solver
    By athinaida in forum Excel Formulas & Functions
    Replies: 7
    Last Post: 06-12-2020, 05:11 AM
  3. [SOLVED] Excel Solver Product Scheduling
    By dgcussblazer in forum Excel Formulas & Functions
    Replies: 13
    Last Post: 08-23-2017, 01:37 PM
  4. Abstaining from using table in solver for workforce scheduling?
    By Sinda in forum Excel - New Users/Basics
    Replies: 1
    Last Post: 03-03-2014, 06:46 PM
  5. Timetable Scheduling - Solver error
    By saikarthik in forum Excel General
    Replies: 0
    Last Post: 08-14-2012, 08:07 PM
  6. Replies: 3
    Last Post: 09-20-2008, 12:18 AM
  7. [SOLVED] Calculating dates - complex scheduling problem
    By jct in forum Excel Formulas & Functions
    Replies: 1
    Last Post: 02-22-2006, 04:10 PM

Tags for this Thread

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts

Search Engine Friendly URLs by vBSEO 3.6.0 RC 1