PHP shift scheduling - sequentially looping through a multidimensional array with numerous subarrays

Question

I am trying to design a shift scheduling program. There are about a dozen potential users (+/- a few), all with specific vacation requirements. There are 4 types of shifts (role1, role2, role3, role4); each role must be covered by a person, a single person cannot cover multiple roles, and some users prefer certain shift sequences (eg. role1-role2-role4-role3 vs. role1-role2-role3-role4), though ultimately the shift sequences can be rearranged if it can't be accommodated within the schedule. Some users can't work certain shifts at all. Each user also has a maximum number of shifts - overall, there isn't much flexibility within the system, so I suspect only a limited number of possible valid solutions.

I've created an array that takes into account mandatory user vacations, so for each calendar date I know which users are in theory available for that shift (at baseline):

   [2020-07-21] => Array
        (
            [0] => Array
                (
                    [role1] => userA
                    [role2] => userB
                    [role3] => userC
                    [role4] => userD
                )

            [1] => Array
                (
                    [role1] => userA
                    [role2] => userB
                    [role3] => userD
                    [role4] => userC
                )

            [2] => Array
                (
                    [role1] => userA
                    [role2] => userC
                    [role3] => userB
                    [role4] => userD
                )

Array is generated by (but this code hasn't had issues - it's when I try to call print_r(cartesian($solutionsArray)); where I run out of memory.

            // Use cartesian product to pick one value from each role array, and then exclude arrays that don't have at least 4 unique users
            foreach ($globalAvailabilityCalendarArray[$globalAvailabilityCalendarDate] as $role => $availableUsersArray) {
                $cartesianProducts = $utilities->cartesian($globalAvailabilityCalendarArray[$globalAvailabilityCalendarDate]);

                foreach ($cartesianProducts as $cartesianProduct) {
                    if(count(array_unique(array_values($cartesianProduct))) !== count($this->roles)) {
                        continue;
                    } else {
                        $solutions[] = $cartesianProduct;
                    }
                }
            }
$solutionsArray[$globalAvailabilityCalendarDate] = array_unique($solutions, SORT_REGULAR);

I have a few problems though:

For this time period, there are 63 work days to take into account. Some days only have 4 people available so the possible combinations are small, but some days may have 10+ available people which means hundreds of possible valid combinations. However, the scheduling requirements of each day depend on what combination has been selected for previous days so it doesn't go over an individual worker's maximum number of shifts. Thus, I am trying to sequentially iterate over each subarray until I find the first possible valid solution (and if possible, other valid solutions for users to compare against) - (eg. [2020-07-01][0] ... [2020-07-02][1]... then [2020-07-01][0] ... [2020][07-02][2]). I have tried calculating cartesian product (Finding cartesian product with PHP associative arrays) which worked for finding available combinations for a single day, but my script runs out of memory when applying it to the whole calendar as there are just too many possible sequences. Is there a less memory intensive alternative?
With my array structure, how can I prioritize shift sequences so that users have a good ratio of shifts (target is role1+role2+role4 / role3 = 2.5) and preferred shift sequence (eg. role1-role2-role3-role4 and avoiding sequential busy shifts like role2-role2-role2-role2-role1)?

"I have tried calculating cartesian product (Finding cartesian product with PHP associative arrays) which worked for finding available combinations for a single day, but my script runs out of memory when applying it to the whole calendar as there are just too many possible sequences. Is there a less memory intensive alternative?" "Here is optimized version of @Jon's cartesian function" => Check at the answer after the accepted answer in the link you supplied? :-) Does that help? — bestprogrammerintheworld, Jun 09 '20 at 04:44
Hey, I tried the original solution, the optimized version and the PHP7 version. I increased the memory limit in PHP to 9GB, but it still ran out of memory. — testtesttest18093870, Jun 09 '20 at 04:47
It seems you got stuck in some kind of infinite loop. Can you please show the code (edit your question) so we might be able to help you out. — bestprogrammerintheworld, Jun 09 '20 at 04:49
The code is simply `print_r(cartesian($solutionsArray));` for that portion. The rest of the code is to just generate $solutionsArray, which works perfectly fine to produce the array above. I have posted a larger excerpt of the array here: https://pastebin.com/bVXdXvvc It's ordered by dates with fewest available users in the pastebin, but some dates further down the list have many more available users and have thousands of possible combinations of users for a single individual date. There are 63 total dates so it gets to be a really large # very quickly. — testtesttest18093870, Jun 09 '20 at 05:05
@bestprogrammerintheworld - updated the answer above. The foreach loop hasn't had any issues generating $solutionsArray - it appears within a few seconds. However, when running cartesian product on the output $solutionsArray (copy/pasted from my link in the post) - that's when it runs out of memory. — testtesttest18093870, Jun 09 '20 at 05:14
So the actual issue is when you're using print_r? How are you increasing the memory limit and have you restarted the webserver after increasing the memory? — bestprogrammerintheworld, Jun 09 '20 at 05:27
If you do another foreach - loop to just print the values. Does that work? — bestprogrammerintheworld, Jun 09 '20 at 05:27
Even without using print_r (I just tried $test = cartesian($solutionsArray);), it still runs out of memory. `Fatal error: Allowed memory size of 9437184000 bytes exhausted (tried to allocate 20480 bytes) in...` Edit: bumping up to 19GB is still the same: `Fatal error: Allowed memory size of 19922944000 bytes exhausted (tried to allocate 20480 bytes)` — testtesttest18093870, Jun 09 '20 at 05:29
If $test = cartesian($solutionsArray) is failing then code inside the function cartesian is the issue. — bestprogrammerintheworld, Jun 09 '20 at 05:51
@bestprogrammerintheworld - I'm using Sergiy's response from the thread directly. The other alternative I can think of is halting the function after each full set of arrays is generated (from day 1-63) to see if it meets all the requirements; if not, then continue to the next sequence of arrays. Not sure how to modify the code to do that though, since it seems to generate all combinations at once — testtesttest18093870, Jun 09 '20 at 06:24
How many elements do you have in your solutionsArray? e.g. what is count(solutionsArray) ? — bestprogrammerintheworld, Jun 09 '20 at 07:23
@bestprogrammerintheworld - There are 63 dates with an average of 365 options per date (~23000 total) — testtesttest18093870, Jun 09 '20 at 08:00

score 1 · Answer 1 · answered Jun 09 '20 at 07:22

If the only problem you have is memory usage when using the cartesian function then you could search for another way to do the cartesian product without consuming that much memory. After a quick search I found a possible solution you could use. https://github.com/bpolaszek/cartesian-product

According to its documentation, you can use it like:

print_r(cartesian_product($solutionsArray)->asArray());

PHP shift scheduling - sequentially looping through a multidimensional array with numerous subarrays

1 Answers1