How to implement 'soft' deadlines in a scheduling (job-shop) solver?

I'm working on a program to solve a scheduling problem. So far with the examples scattered around Github I've been able to get a pretty well working program, but there's one thing I still need.

Currently, when there's no solution that can satisfy all deadlines, the solver returns 0 results. I want the program to return the result that has the least number of tasks going over their deadline, but only if there's no other solution that does satisfy all deadlines. It doesn't matter which task(s) go over deadline, just as few as possible.

I've been thinking about it and I think I have to overhaul a lot of my current logic. Because, currently the solver tries to minimize the total makespan and all the jobs/tasks have the deadline as upper-bound in the interval variables. If I'd change those deadlines to the horizon as upper bound, it would be able to go over deadlines, but it won't do that just only when there's no other solution.

So I've been thinking; do I need to implement some kind of cost-based system? Where a before-deadline minute costs 0 points and an over-deadline minutes costs 2 points or something. And then the objective is to minimize the cost.

But I'm not exactly sure how to implement that. And furthermore, I'd ideally keep the system as I currently have as much as possible and I think the cost-based system would mean a big overhaul. Does someone maybe have some tips for me? Thanks!

I'm afraid I can't share the whole program because it uses code I can't share, but it's C# and highly based on the examples on Github here. Here's the core of it (which does not work on its own):

foreach (var job in unplannedJobs)
            {
                IntVar previousEnd = model.NewIntVar(0, 0, "");

                int minStart = ConvertDateTimeToRelativeInt(job.MinStartdate ?? scheduleFrom, scheduleFrom);
                //int maxStart = ConvertDateTimeToRelativeInt(job.MaxStartdate ?? scheduleFrom, scheduleFrom);
                int deadline = ConvertDateTimeToRelativeInt(job.Deadline, scheduleFrom);

                var tasks = job.SchedulingProduct.SchedulingProductTasks.OrderBy(t => t.SequenceNumber);
                foreach (var task in tasks)
                {
                    var machineConfigs = task.SchedulingTaskMachineConfigurations;

                    int minDuration = machineConfigs.First().Duration * job.Amount;
                    int maxDuration = machineConfigs.First().Duration * job.Amount;

                    foreach (var config in machineConfigs)
                    {
                        int configDuration = config.Duration * job.Amount;
                        minDuration = Math.Min(minDuration, configDuration);
                        maxDuration = Math.Max(maxDuration, configDuration);
                    }

                    // Main interval
                    var nameSuffix = string.Format("_J{0}_T{1}", job.ProductionItemID, task.ProductTaskID);
                    var start = model.NewIntVar(minStart, horizon, "start" + nameSuffix);
                    var duration = model.NewIntVar(minDuration, maxDuration, "duration" + nameSuffix);
                    var end = model.NewIntVar(minStart, deadline, "end" + nameSuffix);
                    var interval = model.NewIntervalVar(start, duration, end, "interval" + nameSuffix);

                    // Store start of solution
                    starts[(job.ProductionItemID, task.ProductTaskID)] = start;

                    if (task.SequenceNumber > taskSequenceStart)
                        model.Add(start >= previousEnd);

                    //Deadline
                    //model.Add(end <= deadline);

                    previousEnd = end;

                    // Creer alternatieve intervals (elke machine/taak combinatie)
                    if (machineConfigs.Count > 1)
                    {
                        var altPresences = new List<IntVar>();

                        foreach (var config in machineConfigs.OrderBy(c => c.MachineID))
                        {
                            var altNameSuffix = string.Format("_J{0}_T{1}_M{2}", job.ProductionItemID, task.ProductTaskID, config.MachineID);
                            var altPresence = model.NewBoolVar("presence" + altNameSuffix);
                            var altStart = model.NewIntVar(minStart, horizon, "start" + altNameSuffix);
                            var altDuration = config.Duration * job.Amount;
                            var altEnd = model.NewIntVar(minStart, deadline, "end" + altNameSuffix);
                            var altInterval = model.NewOptionalIntervalVar(altStart, altDuration, altEnd, altPresence, "interval" + altNameSuffix);
                            altPresences.Add(altPresence);

                            model.Add(start == altStart).OnlyEnforceIf(altPresence);
                            model.Add(duration == altDuration).OnlyEnforceIf(altPresence);
                            model.Add(end == altEnd).OnlyEnforceIf(altPresence);

                            //Deadline
                            //model.Add(altEnd <= deadline);

                            if (!intervalsPerResources.ContainsKey(config.MachineID))
                                intervalsPerResources[config.MachineID] = new List<IntervalVar>();

                            intervalsPerResources[config.MachineID].Add(altInterval);

                            presences[(job.ProductionItemID, task.ProductTaskID, config.MachineID)] = altPresence;
                        }

                        model.Add(LinearExpr.Sum(altPresences) == 1);
                    }
                    else
                    {
                        var config = machineConfigs.First();

                        if (!intervalsPerResources.ContainsKey(config.MachineID))
                            intervalsPerResources[config.MachineID] = new List<IntervalVar>();

                        intervalsPerResources[config.MachineID].Add(interval);

                        presences[(job.ProductionItemID, task.ProductTaskID, config.MachineID)] = model.NewConstant(1);
                    }
                }

                jobEnds.Add(previousEnd);
            }

            foreach (var machine in intervalsPerResources)
            {
                var intervals = machine.Value;
                if (intervals.Count() > 1)
                {
                    model.AddNoOverlap(intervals.Concat(nonWorkingIntervals).ToList());
                    model.AddNoOverlap(intervals.Concat(plannedIntervals).ToList());
                }
            }

            // Create objective
            var makespan = model.NewIntVar(0, horizon, "makespan");
            model.AddMaxEquality(makespan, jobEnds);
            model.Minimize(makespan);

            // Create the solver.
            CpSolver solver = new CpSolver();

            // Set the time limit.
            if (timeLimitInSeconds > 0)
            {
                solver.StringParameters = "max_time_in_seconds:" + timeLimitInSeconds;
            }

            // Solve the problem.
            CpSolverStatus status = solver.Solve(model);

Try creating a boolean that is true when a task is over its deadline and minimize their sum.

@stradivari96 I've been thinking about something like that too yeah, but I'm not sure it'll work very well (if I can get it to work at all, for some reason I seem to have difficulties properly understanding CP, but that aside). The thing is, I want to minimize both total makespan and over-deadline time. If I simply add a boolean 'over deadline' to every job, it would theoretically be possible to schedule a job that's e.g. 24 hours over deadline instead of a solution where e.g. 2 jobs are both 1 hour over deadline, because the 24 hours over deadline solution has less 'over-deadline' booleans and maybe even a lower total makespan.

If that makes sense haha. Maybe I'm overthinking things?

I mean, it's still better than not producing a solution at all so in the worst case I could implement something like that, but it's not ideal.

You could minimize first the number of over deadline tasks and then their makespan. Or alternatively minimize(makespan+(bignumber)*sum(booleans))

Or the other way around, depends of what your priorities are

You could also take a look at: https://github.com/google/or-tools/blob/stable/examples/dotnet/ShiftSchedulingSat.cs

I'm assuming the solver exhausted the search space and found the instance unsatisfiable. This means your problem is over-constrained.

Couple of things you can look into:

Relax the constraints. Simply relax the time windows, ie. permit things to be x time late, or add more machines etc. This is very easy and requires no change to your model. You might try and do this iterativelv. Relax, try and solve, relax more, try and solve etc. This way you can easily see how over-constrained your instances are and how to tune the penalty if you model it as a soft constraint
Model missed deadlines as a soft constraint Combine the make-span and missed deadline into one linear objective function. As in the shift scheduling example @stradivari96 linked to
Model makespan and missed deadlines as a multi‐objective combinatorial optimization (MOCO) problem There are some examples here on how to do it in OscaR-CP as well as a research paper on Multi-Objective Large Neighborhood Search. Not sure if there are any example of how to do it in the OR LCG solver

https://github.com/google/or-tools/blob/46173008fdb15dae1dca0e8fa42a21ed6190b6e4/examples/cpp/jobshop_sat.cc#L227 Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

Le mer. 20 nov. 2019 à 04:55, CervEdin notifications@github.com a écrit :

I'm assuming the solver exhausted the search space and found the instance unsatisfiable. This means your problem is over-constrained.

Couple of things you can look into:

1.

Relax the constraints. Simply relax the time windows, ie. permit things to be x time late, or add more machines etc. This is very easy and requires no change to your model. You might try and do this iterativelv. Relax, try and solve, relax more, try and solve etc. This way you can easily see how over-constrained your instances are and how to tune the penalty if you model it as a soft constraint 2.

Model missed deadlines as a soft constraint Combine the make-span and missed deadline into one linear objective function. As in the shift scheduling example @stradivari96 https://github.com/stradivari96 linked to 3.

Model makespan and missed deadlines as a multi‐objective combinatorial optimization (MOCO) problem There are some examples here https://bitbucket.org/oscarlib/oscar/src/dev/oscar-cp-examples/src/main/scala/oscar/cp/examples/multiobjective/ on how to do it in OscaR-CP as well as a research paper on Multi-Objective Large Neighborhood Search https://www.info.ucl.ac.be/~pschaus/assets/publi/cp13_molns.pdf. Not sure if there are any example of how to do it in the OR LCG solver

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/google/or-tools/issues/1727?email_source=notifications&email_token=ACUPL3PKMF2DHQ4OCPBGFW3QUUXT7A5CNFSM4JPPBTBKYY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGOEER4E2I#issuecomment-555991657, or unsubscribe https://github.com/notifications/unsubscribe-auth/ACUPL3OIPB6KMYOLYDQO2P3QUUXT7ANCNFSM4JPPBTBA .

Thanks for the replies!

I've been thinking and tinkering a bit and I seem to have something working as @stradivari96 initially suggested. I added a boolean to each job whether it was over deadline or not and collected those in a list. I made the deadline constraint only enforcable if it was not over deadline. And lastly I added the sum of the list of over-deadline booleans to the makespan in the minimize objective.

I haven't tested it very thoroughly yet, but from a quick glance it seems to work. It also seems to take more time to get to an optimal solution, but also not sure about that.

It's still not perfect because of the reason I explained in the post above. Ideally I want to minimize the over-deadline time instead of the number of over-deadline jobs. But at the very least it comes up with a solution now.

I'll also take a look at example lperron linked. Thanks!

Yep, the lateness_penalty that Laurent linked should be the best approach.

google / or-tools

How to implement 'soft' deadlines in a scheduling (job-shop) solver? #1727