Originally posted by: mbarszcz1

I wanted to see if somebody could point me in the right direction in developing a model for a scheduling satisfiability problem. I have roughly 66 machines that need to be serviced by 6 mechanics a certain number of times per week. The objective is to maximize the time in between services for each machine to keep costs down. Now each machine is only available to be serviced at certain times during the week which varies by machine, and mechanics can only service one machine at a time.

I know that I can add an objective to maximize a single variable value, but it appears the CP Optimizer doesn't support multiple objectives like maximizing the time between services for each of the 66 machines. Is there a way to add this into the model as a constraint on each machine, or any other recommendations on how to approach this problem?
#CPOptimizer
#DecisionOptimization

Originally posted by: GGR

Hi

Let's me rephrase your problem

The machine have fixed time interval that requires one mechanics
The mechanics serve one machine at a time. let' a->b->c the sequence of services for one mechanics. You want to maximize the delay between service. That is for this mechanic min(startOf(c) - endOf(b), startOf(b) - endOf(a)). Incidently, you does not know the number of service executed by one mechanics in the schedule.

First we model the mechanics

I suppose we have 2 dates origin horizon
There is nbs maximun services per mechanics to fullfill
There is nbm mechanics
There is minimum delay between 2 successive services of one mechanics.
each is a chain of maximun nbs servicea whose duration is in between ptmin and ptmax.

int origin = ...; 

int horizon = ...; 

int delaymin; 

int nbm = ...; 

int nbs = ...;   dvar interval operations[1..nbm][1..nbs] optional in origin..horizon size ptmin..ptmax;   dvar 

int dist[1..nbm][1..nbs-1] in delaymin..(horizon-origin); 
// cost term   maximize min all (i in 1..nbm, j in 1..nbs-1) dist[i, j]; min (i in 1..nbm, j in 1..nbs-1) delayl 
// there is a cost only if service n+1 is due subject to 
{ forall(i in 1..nbm, j in 1..nbs-1) 
{ 
// the chain of intervals for a mechanics including the successor delay endAtStart(operations[i][j], operations[i][j+1], delay[i][j]); presenceOf(operations[i][j]) >= presenceOf(operations[i][j+1]); delay[i][j] <= presenceOf(operations[i][j+1])*delayMin; 
// The services at rank 3 is due only if service at rank 2 is fullfilled 
} 
}

Modeling the machines.
We have nbp machines
We need a tuple set to describe the services of machine

A machine is modelled by a cunjunction of cumul function to tell when something is to do with alwaysXXX constraints that tells by who (how much is one unit).

int npb = ...   tuple Service 
{ 

int machine; 

int start; 

int end; 
};   
{Service
} services = ...;   

int ptmin = min all(s in services) services[s].end - services[s].start; 

int ptmax = min all(s in services) services[s].end - services[s].start;   cumulFunction cumuls[p in 1..npb] = sum all(s in services; s.machine == p) pulse(s.start, s.end, 1); stateFunction status[p in 1..npb];   subject to 
{ forall(p in 1..npb, i in 1..nbm, j in 1..nbs) alwaysIn(cumuls[p], operations[i][j], 1, 1); 
// at least one operator per service alwaysEqual(status[p], operations[i][j], i, true, 

true); 
// at most one operator per machine  
} 

if (delayMin == 0) 
{ 
// either two mechanics could share the same service forall(s in services, p in 1..npb; s.machine == p) alwaysConstant(status[p], s.start, e.end); 
} 
} 
}

Your problem is formally quite interesting as the model is very simple and require only optional interval and integer function. Nevertheless the model is very loose: e.g. never the length and the position on the machine of a service is put in the model of interval variables for the mechanics.
Just like in a MIP (if you are use to) it is possible to add redundant modeling feature (like global cut) that could utterly helps the optimizer.

In fact, we are quite interested in your problem. If you agree sharing data we would be very please.

Hope that helps
#CPOptimizer
#DecisionOptimization

Originally posted by: GGR

Hi

I have made a typo. The integer variable array for the objective function should be named delay.

Sorry about that
#CPOptimizer
#DecisionOptimization

Originally posted by: GGR

Hi

The model I sent you is wrong, sorry for that. I missed a basic rules of design. One interval variable by possible constant interval role in the solution.

In fact, the services must be an alternative of machine per mechanics. This was not true in my model.

So to model a resource, you create all alternative and use an alternative constraint or the trick cumul expression/state function to associate with actual service on one machine.

int npb = ...; 
// number of machine 

int nbm = ...; 
// number of mechanics tuple Service 
{ 

int machine; 

int start; 

int end; 
}; 
{Service
} services = ...;   

int horizon = max (s in Services) s.end; 

int origin = min (s in Services) s.end;   dvar interval operations[s in Services][1...nbm] optional in s.start...s.end size s.end-s.start;     
//model with alternative dvar interval services[Services]     subject to 
{ forall(s in Services) alternative(services[s], all(i in nbm) operations[s][i]); 
}

Then you model the mechanics similarly as previously, using the cumul/state function trick for linking mechanics chain interval but also a no-overlap constraint.

//model with noOverlap     tuple Distance 
{ 

int start; 

int end; 

int value 
};   

int delayMin = ...;   
{Distance
} DelayMin = 
{<0, 0, delayMin>
};   dvar sequence mechanics[i in 1..nbm] in all (s in service) operations[s][i];     maximize 
// an upper bound of the term (s, i) objective is horizon 
// an absent interval term cost or the last of the sequence term must  
// greater than horizon 
// the last of the sequence term  min (s in services, i in 1...nbm) startOfNext(mechanics[i], operations[s][i], 2*horizon , horizon) - endOf(operations[s][i], 0); 
// if operations[s][i] is absent term[s][i] = horizon 
// if operations[s][i] is kast in sequence term[s][i] = 2*horizon - 
//    endOf(operations[s][i]) >= horizon  subject to 
{ forall (i in 1...nbm) noOverlap(mechanics, DelayMin); 
}

#CPOptimizer
#DecisionOptimization