Originally posted by: stevedwards

Hi there,

I am interested in understanding whether there is a recommended way to enforce serial schedule generation schemes in CP Optimizer (at least for finding an initial feasible solution).

I'll refer to job shops with makespan objective to make the question explicit.

So say you have a set of jobs J and each job consists of an ordered set of m Operations. So (i,j) refers to the i'th operation of the j'th job. A serial schedule generation scheme (SSGS) is essentially a priority rule heuristic that schedules all the operations from one job before trying to schedule the operations from the other jobs. Whereas a parallel schedule generation scheme (PSGS) is time-oriented, i.e. for a time 't', keeps track of the operations that have been completed C(t), processing P(t), and candidates C(t), and then selects candidates based on some evaluation scheme. From what I have read / understand CP Optimizer's default search works like a very clever / general PSGS.

Generally speaking (in my experience) PSGSs obtain better results than SSGSs. However sometimes there are a number of practical benefits of SSGSs, e.g., partial schedules are feasible for jobs that are completed, when feasibility is an issue (e.g. many maximum time-lags exist) SSGSs are useful for finding feasible solutions quicker, etc.

Hence returning to my question, is there a recommended way to encourage CP Optimizer to use SSGSs? I can think of two ways,

1. Search Phases - addSearchPhase(J1, J2, J3). However this feels a bit too hard coded and often it is impossible to know which job to schedule before the other.

2. Optional Interval Variables - Essentially make all operations optional, add presenceOf constraints to ensure that if one operation from a job is present then all of the operations must be present, and then add a penalty to the objective function if a job is absent which would account for simply scheduling absent jobs one by one at the end of the schedule.

Is there a better way that I am missing?

Originally posted by: PhilippeLaborie

CP Optimizer runs a set of heuristics before entering the optimization step. And most of these heuristics uses a SSGS: they compute a topological sort of the activities in the precedence graph according to some heuristic (some will consider the activities on a job by job base) and go through this topological sort and fix the activities at their earliest start time. As you say, this can be useful in case of maximal time lags as in this case, it is easier to find a feasible solution if one fix the activity on a (strongly) connected component base.

Originally posted by: stevedwards

Hi Philippe,

Thank you for your reply.

Ohhh I see.

In that case is there any method to access partial solutions when finding an initial solution after a certain amount of computation time?

In my experience most of the time CP Optimizer manages to find solutions within a reasonable amount of time however sometimes it still hasn't found a schedule after a couple of minutes which isn't acceptable in practice. I would prefer a partial solution with 80+% of the operations scheduled than nothing.

Maybe my question should be, what is the recommended approach when an initial feasible schedule cannot be found after a given amount of time?

Thanks again,

Steven

Originally posted by: PhilippeLaborie

Ok I see. Then yes, the easiest way to go would be to have all interval variables optional and minimize the number of unscheduled activities. A general way to do that could be to ensure that only the first activities in the schedule are executed, so it you have a precedence endBeforeStart(a,b), you would add an implication constraint presenceOf(b)=>presenceOf(a). Then you could solve your problem in two steps:

1- minimize the number of unscheduled activities ( n - sum(i ...) presenceOf(act[i]) )

2- start from the set of activities from step 1 (starting point) to optimize the regular criterion

Note that in case it is difficult to schedule all activities, step 1 may be a good alternative to schedule everything (it may well be that it is difficult to schedule all activities from scratch but that the minimization finds a solution with 0 unscheduled activities as it works in a very different way)

Originally posted by: stevedwards

Very interesting!

Will have a play with this idea. Thank you.