Originally posted by: llDubs

Hi,

I've been stuck on this for a couple of days and I could really use some help..

My problem is patient scheduling.  

  - each patient has a set of tasks 

 - only a subset of tasks require a unary resource

- there is a set of workers who can perform each task type with some capacity

- only some workers have access to some resources - so if a task is allocated to resource it must also be assigned to a worker with access to that resource tyype

- each task is mapped to a set of valid resources

 - each resource is mapped to a set of valid workers

I've tried to model this using multiple alternative constraints but I am getting a conflict.

The conflict comes in when more than one worker has access to the same resource. However, I've specified for every task requiring a resource, only one allocation is allowed.  But when I try to pick a valid worker for that allocation (which is optional), it causes issues.   I'm quite stuck and not sure what to try next.

Any help would be much appreciated.

Thanks,

Leah

using CP;


 
range slots = 1..156;

/********************* Workers ************************************************/
         //define all workers
         tuple worker {
          key string worker_id;
          string worker_type;
        };
        
         //each worker/task type has a capacity assosciated with it
         tuple worker_capacity{
                string worker_id;
                string task_name;
                int task_capacity; 
         };
          
          //define the type of tasks workers of certain type can perform
          //important for data validation
          tuple task_definitions {
                string worker_type;
                string task_name;
         };
         
         //final tuple definition that combines input from all above
          tuple worker_tasks{
                string worker_id;
                string worker_type;
                string task_name;
                int capacity_level;
         }
         
         
          {task_definitions} TaskDefinitions = ...;
          {worker_capacity} WorkerCapacity = ...; 
          {worker} Workers = ...; 
          
          {worker_tasks} WorkerTasks = 
          {<w,ty,ta, c> |      <ty,ta> in TaskDefinitions,<w,ta,c> in WorkerCapacity};
          
          
/********************* Tasks************************************************/     
         tuple task{
          key int task_id;
          int patient_id;
          string task_name;
          int prec_id;
          int seq_id;    
          int dur;
         }  
         

         tuple task_attribute{
                int task_id; 
                string attribute;
         }
         
        
         
        {task_attribute} TaskAttributes= ...;
        {task} Tasks = ...;
        
         {int} Patients = {t.patient_id | t in Tasks};
        /************Resources***********************/
        tuple resource{
                key int id;
                string name;
                string type;
                string owner;   //owner can be worker id or worker type
        }
        
        


        {resource} Resources = ...;
        
        /*****************Valid Combos*********************************/
         tuple work_task_combo{
           task Task;
           worker_tasks WT;   
         }
         
         tuple alloc{
                task t;
                resource r;     
         }
         
        tuple resource_worker_map{
            resource r;
            worker_tasks wt;
    }
 
        {work_task_combo} WorkerTaskMatch = 
        {<t,wd> | t in Tasks, 
                        wd in WorkerTasks: t.task_name==wd.task_name};       
                        
        
    


   {alloc} Allocations = {<t,r> | t in Tasks, 
                                r in Resources,
                                a in TaskAttributes:
                                t.task_id == a.task_id &&
                                r.type== a.attribute}
                                                                        
                                                union
                                                                        
                                {<t,r> | t in Tasks,
                                         r in Resources:
                                        t.task_name == "mixing" &&
                                        r.type == "HOOD"};  
                                                                                        


        {resource_worker_map} ResourceWorkers =
                 {<r, wt> | wt in WorkerTasks,
                                                r in Resources:
                                                                 (wt.worker_type == r.owner ||wt.worker_id ==r.owner)};
        
        
        

        {task} TasksReqResource = {a.t | a in Allocations};
        
        
         dvar interval patient[Patients];
         dvar interval appt[t in Tasks] in slots  size t.dur; 
         dvar interval work_task[wt in WorkerTaskMatch] optional 
                                                                in slots;
         dvar interval allocations[a in Allocations] optional in slots size a.t.dur;
         dvar sequence resource_seq[r in Resources] in all( a in Allocations: a.r == r) allocations[a];
         
         cumulFunction workerCapacity[wt in WorkerTasks] = 
                sum(t in Tasks:  t.task_name== wt.task_name) pulse(work_task[<t,wt>],1);
         
         //minimize makespan
         minimize max(t in Tasks) endOf(appt[t]);
          
         subject to{
         
            forall(p in Patients)
             span(patient[p], all(t in Tasks: t.patient_id==p)appt[t]);
                          
                //one worker per task (constrained for all tasks)
                forall( t in Tasks)
                        oneWorkerperTask:
                        alternative(appt[t], 
                                all(wtc in WorkerTaskMatch: wtc.Task==t) work_task[wtc]);
           
            //choose 1 valid alternative allocation for each task requiring a resource
                 forall(t in TasksReqResource)
                    taskResource:
                    alternative(appt[t], all(a in Allocations: a.t==t) allocations[a]);
                
         //for any present allocation, choose one valid worker
         forall(a in Allocations)
                allocResWorker:
                        alternative(allocations[a], 
                        all(s in ResourceWorkers: s.r == a.r)  work_task[<a.t, s.wt>],1);
                
        //resources are unary
            forall(r in Resources)
              noOverlap(resource_seq[r]);
                                            
            //for each worker task the number of assigned tasks cannto exceed 
            // task capacity
                forall(wt in WorkerTasks)
                        resource_usage:
                                workerCapacity[wt]<= wt.capacity_level;
};   

Originally posted by: GGR

Hi

Sorry for the late answer because of a technical problem internally.

if understand well your problem a task require a worker (a unary resource) which use some tools suited for the task

I suggest you design the model by successive alternative. Roughly your program would look like

tuple TaskWorker  { // a worker qualified for a task
 int task;
 int worker;
}

{TaskWorker} TW  = ...;

tuple TaskRes  { // a resource able to process a task
 int task;
 int resource;
 int pt; // the processing time
}

{TaskRes } TR  = ...;

tuple WorkRes { // a resource reachable by a worker
 int worker
 int resource;
}

{WorkRes} WR = ...;

dvar interval task{1..nbtask]
dvar interval taskw[TW] optional;
dvar interval taskr[TR] optional;
dvar interval tasktwr[<tw, tr>: tw in TR, tr in TR, tw.task == wr. task] optional size wr.pt;

// that is the combo mapping is made thanks to a task matching

subject to { // I supposeworker and resource are unary resources

 /*.. the span and precedence constraints of the tasks model ..*/

 alternative(t in 1..nbtask, all (tw in TW, tw.task == task) taskw[tw]); // task alternative of worker
 alternative(t in 1..nbtask, all (tr in TR, tr.task == task) taskr[tr]); // task alternative of resource
 sum all (t in 1..nbtasks) pulse(task[t],1)] <= min(nbworkers, nbresources); // amount of work for a worker

 //the submodel of a worker
 forall(w in 1..nbWorkers) {
  forall(tw in TW, TW.worker = w)
    alternative(taskw[tw in TW], all (tr in TR, tr.task = tw.task) taskrw[<tr, tw>]) // worker operation alternative of suited resource
 noOverlap(all(tw in TW, tw.worker = w) taskw[tw]);
 /*.. other conditions on workers */
}

 /*.. similar sub model as worker for the resources ..*/

}

Hope that help.

Originally posted by: llDubs

Hi GGR,

Thanks so much for the help.  I ended up doing something a bit similar to your solution.  The only difference is that not all tasks require resources so I only need a second alternative constraint for those talks.  But your clear and simple response helped me organize my thoughts a bit.

Thanks for taking the time to reply,

Leah