Originally posted by: sds_rohit

Hi,

I have a following problem:-

Workers work on Task and they accumulate worktime = sum of time duration of the tasks performed.
After certain time when worktime has reached its maxvalue, workers need to rest. After resting their Worktime gets reset to ZERO. And they can work again on Tasks and accumulate hours.

I have modeled the Worktime using the cumulative function incrementing at STEPATSTART of each Task interval variable with STEPVALUE = TASK DURATION.

For the REST, I have modeled that also as a TASK, with a fixed duration. However, I am struggling to RESET the worktime to ZERO at the STEPATSTART of the REST.
Please help. In-case of better modelling technique, please suggest.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,
The model you suggest is possible. To model an interval variable R that resets a cumul function F to 0 you can use the conjunction of a startAtStart with a range (rather than a fixed value) and an alwaysIn constraint that states F should remain equal to 0 furing interval R:

• Contribution of rest interval R to the cumul function F: -stepAtStart(R,0,maxvalue)
• Constraint stating that the cumul function should be equal to 0 during R: alwaysIn(F,R,0,0)

This last constraint will "fix" the actual height of the stepAtStart so that it actually resets the level of the cumul function F to 0.

The above model may result in weak inferences in the engine. If your problem is not very big and if you can compute in advance a reasonable upper bound on the number n of "working" periods, you could also define a chain of n interval variables representing the possible working periods and post precedence constraint with a minimal delay (representing the minimal rest time) between consecutive intervals in this chain. Then, for each activity Ai you can define a set of n optional intervals Ai1,...,Ain where Aij represents the execution of activity Ai in the jth working period. You then have the following constraints:

• Each activity is executed in exactely one working period: alternative(Ai, [Ai1,...,Ain])
• Each working period Wj spans the activities executed in this period: span(Wj, [A1j,A2j,...,Aij,...])
• The total working duration in each period Wj is constrained by the maximal working duration: sum(i) lengthOf(Aij) <= maxvalue

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: sds_rohit

Thanks for your reply.

In my model each TASK has a START-CITY and END-CITY. Workers travel from CITY A to B while doing their task.
Due to this CITY factor, Task 2 cannot follow Task 1 if END-CITY of Task 1 is not equal to START-CITY of Task 2. Furthermore, if the CITY were same, then after TASK-1 there is certain WAIT period (different and depending upon Tasks). In order to model this, I am trying to use Transition times (forbid transitions if CITY doesn't match) as detailed your following link :-

http://www.ibm.com/developerworks/forums/thread.jspa?messageID=14599503

Kindly, suggest in-case of any better method to model.

Now, I am facing a problem :- Rest for a worker after certain no of tasks( Total worktime >= MaxValue ) is allowed at certain CITIES only. Furthermore, simultaneous no of workers resting at any city is limited by the lodging facility available.

Model 1:- Modelling with Cumulative function :-
I thought, I will consider REST also as a TASK.
a) Will make REST as a OPTIONAL variable for each CITY and each Worker.
b) Transition for forbidden and non-forbidden case can then be handled similar to other tasks.
c) Minimize the no of the REST period chosen.
d) Cumulative Function for each CITY :- pulse for REST tasks for that CITY :- Limited by lodging facility available.

Model 2 (as suggest by you) :- Modelling with Working Period with Rest in-between:-
I am clueless about following :-
a) How to handle CITY effect as REST is not more a task its a time gap between two Working period. How to make sure REST happens only at allowed CITIES ?
b) How to limit the simultaneous REST by lodging facility ?

Please suggest how to solve these problems in MODEL 2 ?
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

In model 2:

a) How to handle CITY effect as REST is not more a task its a time gap between two Working period. How to make sure REST happens only at allowed CITIES ?

You can use interval variables instead of a time gap between the two working periods. Then, you can make sure the rest happens only in an allowed city by stating this rest interval is actually an alternative of optional intervals, one for each allowed city. These intervals for triplets <worker,rest interval,city> are also added to the sequence variable representing the activity of each worker.

b) How to limit the simultaneous REST by lodging facility ?

Once you have (optional) interval variable for each possible pair rest interval / allowed city, you can easily create a cumul function per city that sums the number of simultaneous rests at this city.

I attach an OPL project that contains two models to illustrate the two possible approaches:

• citiesCumul.mod is the approach 1 with a cumul function for the working time
• citiesSpan.mod is the approach 2 with span and alternatives

Some comments are available in the models. I randomly generated some data in Common.mod.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: sds_rohit

Thanks a lot indeed for your support.

I will go through your suggestions/code in details.

I wanted to confirm that as per your "last but 1" message, model 2 will have better performance that model 1. If you could detail why is such behavior.
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Well, I did not really said model 2 will have better performance. It is just that it will result in stronger inference in the engine because of the additional optional interval variables that represent the tasks "if" they were executed in a given working period. The engine can infer some information on the bounds of these variables (e.g. end max of task 4 if it was executed in the 2nd working period of worker 1) and propagate it to the others variables in the model. In model 1, these interval variables are not available. But of course, the multiplication of decision variables in the model also has a cost and the engine will spend more time at each search node to perform those inferences, and maybe those inferences are not really useful for the search. So, if to speak of global performance, one has to balance the two effects. What is clear is that if you have a large number of potential working periods (in the worst case, 1 working period for each of the n tasks), then in model 2 you will have n^2 such intervals per worker so it won't scale well. That's what I meant when saying "if your problem is not very big and if you can compute in advance a reasonable upper bound on the number of working periods ...". The best is to try the two models.

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: sds_rohit

Hello,

I have implemented the two models suggested by you, in our last conversation, on my sample data.

My observation:-
1. Our expectation from both models is that each TASK should get a worker. My sample data size has 30 workers and 1341 tasks. My Target time for completion is max 1 hrs. I ran both models for 1 hour (3600 seconds) and still they were unable to assign a worker to every task.

2. Out of the two models (cumulative and span) I get better performance with the cumulative one.

3. I believe there is some problem with rest tasks as we are giving them a big interval size. I think restricting their size will help speed up the process. To check the same, I made a new model without any rest tasks and then ran on my sample data, this model was able to assign worker to each task within 1 hrs.

Attachments:-
1) I am attaching a “Result BookKeeping.xlsx” where the summary of performance is presented for each of the three models.

2) I am attaching the models (‘Cities_Cumul’, ‘Cities_ Span’, ‘Cities_Test’). The input is provided through a common XL sheet (“30 workers 7 days.xlsx”), also attached here.

3) I am also attaching the part of OPL codes written in text files, so in case of any problem in running the attached .mod files, you can still be able to run through these text files.

Issues :-
Model 1 (Cities_Cumul) and Model 2 (Cities_ Span) is showing very poor performance for our sample data of 30 workers and 1341 tasks.

Please suggest us how to improve the performance of both the models.
#DecisionOptimization
#OPLusingCPOptimizer