Originally posted by: sds_rohit

Hello,

I have implemented the two models suggested in the following link, on my sample data.

https://www.ibm.com/developerworks/forums/thread.jspa?messageID=14627727

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

Originally posted by: SystemAdmin

Hello,
Looking at your data, it seems that on this instance all tasks have fixed start and end dates. Is it a characteristic of the problem? If this is the case, this changes the nature of the problem as it is more an allocation problem (allocate tasks to workers) rather than a scheduling one (as all dates are known) and alternative and probably more efficient models are possible.

Philippe
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: sds_rohit

Thanks for your reply.

I am trying to develop the code in steps. I was thinking that in

STEP 1) I will solve it as tasks with fixed timing.

STEP 2) Then I will allow varying the time of the task, as well.

I felt that CP optimizer as the perfect modelling tool for my problem. However, looks like CP optimizer though models the problem perfectly but is able to solve smaller problem size, only. When the problem is of realistic problem size, CP optimizer is just not able to solve it in acceptable time limit.

Is there something wrong in my approach ? Is it that at larger problem size, Operation Research tools like CPLEX is better than CP optimizer ?

Kindly, guide me on my problem. Can you confirm that CP is not the correct tool for the problem, I am trying to solve ?
#DecisionOptimization
#OPLusingCPOptimizer

Originally posted by: SystemAdmin

Hello,
I think solving the problem in several steps is a good approach. If some initial fixed times for the tasks are available, it indeed makes sense to use them in a first step, even if part of the problem will consist in "improving them".

You could also consider decomposing the problem by first working on an allocation of tasks to workers or at least partitioning the set of workers on the set of tasks and solve the different problems independently. Maybe this can also be related with a spatial partitioning of the global problem.

For solving the problem with fixed times for task, a CPLEX model, or a CP Optimizer model with integer variables may be worth considering indeed. But for solving a version where tasks are not fixed, I think a CP Optimizer model with interval variables, like the one you have, will be better than a CPLEX or CP Optimizer one with integer variables. Your problem is quite challenging because you need to do scheduling (that is: finding start/end dates) of heteregenous types of activities (tasks, rests) and workers allocation + there is also a feasibility problem: finding a solution is also a combinatorial problem due to the fact workers only travel from one city to the other when executing a task (this is more like a flow problem here).

For info, I slightly adapted your model (with cumul functions) by simply adding a (very bad) starting point solution where none of the tasks are executed and letting the automatic search inserting new tasks to be scheduled in the solution. I did that because I noticed the engine had difficulties to find a first solution even in case the tasks are optional. With this starting point, after a few minutes it manages to schedule, say about half of the tasks and keep on improving but I did not let it run for 1h. The model is attached.

Philippe
#DecisionOptimization
#OPLusingCPOptimizer