Decision Optimization

 View Only
  • 1.  Scheduling with machines and workers calendars

    Posted Thu February 22, 2024 03:41 PM

    Hi all,

    This is my first time seeking help online, so please be patient if this isn't the correct format.

    I'm working with the IBM CP Decision Optimization along with Docplex.

    I've developed a functioning model for scheduling tasks on machines, incorporating optional alternative intervals for each task on the machines where the task can be executed. These task_machine optional intervals include an intensity parameter subject to the machine's availability, with specific periods during which the task is forbidden to start or end.

    Additionally, I've established constraints for the total number of workers allowed. Since tasks are executed by machines, and a worker can operate multiple machines, I've managed this with the sum pulse of all task_operator_usage percentage, which has proven to be effective.

    However, I'm encountering difficulties in modeling workers' availability over time. I've attempted various methods, but using pulse/step_at_start/step_at_end doesn't suit my needs, as operations may extend into non-working periods for machines. I need a way to ensure at any given time that the number of workers does not exceed the limit within a specified interval, based on an array of tuples like (start, end, workers). For every operation, I have a dictionary indicating the percentage of a worker's supervision required.

    Any guidance on how to model this aspect of worker availability effectively would be greatly appreciated.

    TL;DR;
    Is there a way to model workers availability over time when intervals are preemptive due to already existing machines calendars?

    I found this discussions but don't understand how:

    https://community.ibm.com/community/user/ai-datascience/discussion/renewables#bma067e0c4-3284-4040-98e2-f8b0ce8849a7
    https://community.ibm.com/community/user/ai-datascience/discussion/splitting-up-tasks-using-cp-optimizer#bm72f091e1-6591-4e4e-8546-ec4748397b89

    Example where to limit the workers.



    ------------------------------
    Eugeniu Grigoras
    ------------------------------



  • 2.  RE: Scheduling with machines and workers calendars

    Posted Tue February 27, 2024 08:33 AM

    Hello,

    For each worker and each possible machine, you must define a specific calendar that takes into account breaks from both calendars (each time period of this new calendar corresponds to an available time period for the worker and the machine).

    Then, you must use intensity functions for each alternative (worker, machine). Use the following functions: forbid_start and forbid_end, to forbid an interval variable from starting or ending during specified time periods (breaks).

    Within the distribution, in the CPLEX_Studio221\python\examples\cp\visu directory, the "house_building_calendar.py" example uses an intensity function to model worker availability over time.



    ------------------------------
    Thierry Sola
    ------------------------------



  • 3.  RE: Scheduling with machines and workers calendars

    Posted Tue February 27, 2024 09:13 AM

    Hi Thierry,

    Thanks a lot but this is not the case as a machines can process one job at a time (the alternative machine interval) but a worker can work (supervise) multiple machines. It's like the money example in the scheduling_tuto but that example does not work for me. Money is a non-renewable resource and workers are renewable resource, so if i follow the scheduling_tuto with money example and use money_cumul -= step_at_start to decrease the money value (in my case available workers) it works, but i can't return the worker using money_cumul += step_at_end as the job intervals might overflow machine unavailability and end in a different workers turns. I know it is a difficult problem even in the literature where this is named as RCPSP (Resource constrained project scheduling problem) or DRCSP (Dual resource constrained scheduling problem).



    ------------------------------
    Eugeniu Grigoras
    ------------------------------



  • 4.  RE: Scheduling with machines and workers calendars

    Posted Wed February 28, 2024 12:29 PM

    Hello Eugeniu,

    You mention that "machines can process one job at a time (the alternative machine interval) but a worker can work (supervise) multiple machines." If I well understand a job can be processed on several machines and requires a worker. This worker can be the same if the job is processed on machine m1 or m2 for instance.

    If I well understood, there are "machine's availability" and "worker's availability".

    Why it is important to synchronize calendars?

    Let us consider a task (job J) that requires the resource R1 (machine M1) and a resource R2 (worker W1).

    Calendars are expressed in days.

    Suppose there is a break on machine M1 (maintenance) between day 7 and day 8 (Sunday and Monday).

    Suppose the worker W1 doesn't work on weekend (Saturday and Sunday) between day 6 and day 7.

    If the processing time of the job J is equal to 5 days, then J [1: 3 -- (5)7 --> 10] is a solution.

     Unfortunately, this is not a solution because on day 6 the machine M1 is available but not the worker W1 and on day 8 the worker W1 is available but not the machine M1.

    From what you've written, I think you have a pool of workers with the same availability. In this case you should just use pulse and not use step_at_start and step_at_end.



    ------------------------------
    Thierry Sola
    ------------------------------



  • 5.  RE: Scheduling with machines and workers calendars

    Posted Wed February 28, 2024 12:50 PM

    Hi Thierry,

    The workers doesn't necessarily have the same availability. 

    Please follow this thread (from response N. 3) as I have exactly the same problem.
    https://community.ibm.com/community/user/ai-datascience/discussion/splitting-up-tasks-using-cp-optimizer

    In response N. 8 he explains the same problem i have encountered with pulse.
    In response N. 9 a solution is proposed by "prolonging working_hours records by the following shift"

    I don't understand how in response N. 10 this is done:
    "I added pulses to the times in between the single shifts and my code now works as I wish."

    Thanks again!



    ------------------------------
    Eugeniu Grigoras
    ------------------------------



  • 6.  RE: Scheduling with machines and workers calendars

    Posted Fri March 01, 2024 10:17 AM

    Hello Eugeniu,

                   In answer N.8, a cumul function is added to model worker availability.

    cumulFunction usage_workers = sum(j in Tasks) pulse(tasks[j],1);

    cumulFunction  availability_workers = sum(a in working_hours)(pulse(a.s, a.e, a.p));

    with the following constraint: availability_workers - usage_workers >= 0;

    where "The set "working_hours" contains tuples created in an execute block right before that contain the working hours as follow: <"start", "end", "number of workers present from start to end">."

    Consider two consecutive tuples within set "working_hours" where:

    <s1, e1, nbW1> and <s2, e2, nbW2> where s1< e1 < s2 < e2, 1 < nbW1 and 1 < nbW2.

    This implies that there is no worker available between e1 and s2.

    In answer N.4, Petr explains that: "the problem in your case is the fact that tasks have size specified, it should be enough to specify size on tasks_opt (or vice versa: specify size on tasks but do not on tasks_opt)."

    In response N.5, it is what was done.

    dvar interval tasks[j in Tasks] in 1..(maxint div 2) -1;

    When a task is "pulsed" on a resource, then this task requires this resource from its start date to its end date. This implies that no task (in Tasks) can overlap the period [e1, s2[.

    In this case, the proposed solution consisted of increasing the end of the tuples of the "working_hours" set.



    ------------------------------
    Thierry Sola
    ------------------------------



  • 7.  RE: Scheduling with machines and workers calendars

    Posted Mon March 04, 2024 04:31 AM

    Hello Thierry,

    It was so easy, you're a genius!



    ------------------------------
    Eugeniu Grigoras
    ------------------------------