JobShop Scheduling in C#

[Wojciech]

Hello,

I just started to play with or-tools week ago. It seems to be really interesting tool, especially is open source! I am trying to do JobShop scheduling in C#. As an example I use   chapter 6 of User Manual which is shown in C++. But what is funny I can't get any results. What I do is the following:

Solver solver = new Solver("Scheduling");

IntervalVar[] tasks = new IntervalVar[taskCount];

List<IntVar> all_ends = new List<IntVar>();

int i = 0;

foreach(Task t in myTaskList)

{

   tasks[i] = solver.MakeFixedInterval(0, (long)t.Duration, t.Name);

   if (t.Successors.Count <= 0)

      all_ends.Add(tasks[i].EndExpr().Var());

   //solver.Add(solver.MakeGreaterOrEqual(tasks[i].StartExpr(), 1)); // { 1 }

   i++;

}

IntVar objective_var = solver.MakeMax(all_ends.ToArray()).Var();

OptimizeVar objective_monitor = solver.MakeMinimize(objective_var, 1);

DecisionBuilder obj_phase = solver.MakePhase(objective_var, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

const int kLogFrequency = 999999999;

SearchMonitor search_log = solver.MakeSearchLog(kLogFrequency, objective_monitor);

SolutionCollector collector = solver.MakeLastSolutionCollector();

collector.AddObjective(objective_var);

  

if (solver.Solve(obj_phase, objective_monitor))

{

Console.Out.WriteLine("Solution: ");

foreach(IntervalVar t in tasks)

Console.Out.WriteLine(t.ToString());

}else

{

        Console.Out.WriteLine("Can not find a solution");

}

So actually right now if I don't have any constraints it just returns me all tasks with start 0 and duration seted in the loop. But if I add any even very simple (in my point of view - like the one commented) constraint it always prints me out "Can not find a solution". There is about 15 tasks right now, normaly I would like to add also Disjunctive and Conjunctive constraints, but I didnt add them heare. For me is strange that even very simple constraint show doesn't work. I am pretty sure that I don't know or-tools good yet and I did some stupid mistake. 

Thank you in advice for any response.

[Nikolaj van Omme]

Hi Wojciech,

Your code is incomplete. Basically, you need to rank your IntervalVar (the tasks) *before* you can optimize

IntVar objective_var = solver.MakeMax(all_ends.ToArray()).Var();

You could write the following
 
DecisionBuilder sequence_phase = solver.MakePhase(all_sequences, Solver.SEQUENCE_DEFAULT);

and then combine the two DecisionBuilder  one *after* the other:

DecisionBuilder main_phase =
solver.Compose(sequence_phase, obj_phase);

Don't hesitate to come back if this is not all too clear.

Nikolaj

[Wojciech]

Thank you for your response. Actually you are right. My code is incomplete because I was trying to remove some code to run the simplest possible case and later on I have submited incomplete code. The problem was that I created interval variables like that:

IntervalVar task = solver.MakeFixedDurationIntervalVar(0, long.MaxValue, duration, false, name);

so the horizon is too high if I use lower value it works. For example:

IntervalVar task = solver.MakeFixedDurationIntervalVar(0, 1000000, duration, false, name); 

Now my question is. There is member Performed. May I use it somehow to find out which of the tasks will do my schedule optimal? I mean I have a Job1 and Job 1 can be done by 3 diffrent tasks on 3 diffrent Machines. For example:

Task 1 - Machine 1 - Duration 30 min

Task 2 - Machine 2 - Duration 20 min

Task 3 - Machine 3 - Duration 50 min

I need to choose one of them. And it is not obvious that Task 2 in most optimal. Because in this time Machine 2 can be busy and if i pu there task 2 Makespan will be bigger. But in the same time there could be a gap on machine 3 and I can put Task 3 there what will not affect Makespan.

I really appreciate your answer!

[Nikolaj van Omme]

Hello,

On 12-08-29 03:13 AM, Wojciech wrote:
> Thank you for your response. Actually you are right. My code is
> incomplete because I was trying to remove some code to run the
> simplest possible case and later on I have submited incomplete code.
> The problem was that I created interval variables like that:
>
> IntervalVar task = solver.MakeFixedDurationIntervalVar(0,
> long.MaxValue, duration, false, name);
>
> so the horizon is too high if I use lower value it works. For example:
>
> IntervalVar task = solver.MakeFixedDurationIntervalVar(0, 1000000,
> duration, false, name);

I'm not a specialist. I guess this is normal as internally the limit is
kintmax in c++.

>
> Now my question is. There is member Performed.

From the source code:

// ---------- Interval Var ----------

// An interval var is often used in scheduling. Its main
// characteristics are its start position, its duration and its end
// date. All these characteristics can be queried, set and demons can
// be posted on their modifications. An important aspect is
// optionality. An interval var can be performed or not. If
// unperformed, then it simply does not exist. Its characteristics
// cannot be accessed anymore. An interval var is automatically marked
// as unperformed when it is not consistent anymore (start greater
// than end, duration < 0...)

> May I use it somehow to find out which of the tasks will do my
> schedule optimal?

If I understood you question, I don't think so.

> I mean I have a Job1 and Job 1 can be done by 3 diffrent tasks on 3
> diffrent Machines. For example:
>
> Task 1 - Machine 1 - Duration 30 min
> Task 2 - Machine 2 - Duration 20 min
> Task 3 - Machine 3 - Duration 50 min
>
> I need to choose one of them.

What do you mean by "I need to choose one of them"? Don't you want the
solver to find an optimal/good solution for you?

> And it is not obvious that Task 2 in most optimal. Because in this
> time Machine 2 can be busy and if i pu there task 2 Makespan will be
> bigger. But in the same time there could be a gap on machine 3 and I
> can put Task 3 there what will not affect Makespan.
>
> I really appreciate your answer!

You're welcome. Hope it helps. My priority now is not to translate the
C++ code into C# but it is on my list of things to do.

Best,

Nikolaj

[Wojciech R.]

Yes, I want solver to choose the optimal solution, but to get optimal solution in my case I would like the solver to choose between 3 (or any number of) alternative tasks. 

2012/8/29 Nikolaj van Omme <nikolaj....@gmail.com>

[Wojciech]

Yes, I want solver to choose the optimal solution, but to get optimal solution in my case I would like the solver to choose between 3 (or any number of) alternative tasks. 

So actually I'm trying to find out the easiest and the most efficient way of doing that in or-tools constraint solver.  

[Daniel Mota]

Why not use "Disjunctive Graph" to solve it?

--
_______________________________
M. Sc. Daniel de Oliveira Mota
UFJF / NCA&T
Management Science - Operational Research

"The best way to predict the future is to invent it" Alan Key

[Wojciech R.]

I just fought that maybe there is a ready solution to add alternative tasks and let solver choose one of them to get optimal solution. Something like MakeDisjunctive which avoids overlaping. 

2012/8/30 Daniel Mota <danielmot...@gmail.com>

Why not use "Disjunctive Graph" to solve it? 

How would you do it? Implementing your own graph or using or-tools somehow? Sorry if my questions are not so smart but I am not an expert in OR.

[Nikolaj van Omme]

Hello,

Adding disjunctive constraints without solving the model doesn't work. You need a DecisionBuilder to rank your IntervalVars.

Best,

Nikolaj

[Lukas Hollenstein]

 Hi, I'm completely new to or-tools and constraint programming. But at least I think I managed to translate the C++ JobShop example into C# (see below and feel free to include it in the examples).

My question is, how do I access information on the solution, like the starting times of the tasks per machine? Thanks!

using System;

using System.Collections.Generic;

using Google.OrTools.ConstraintSolver;

class Machine

{

    public long Id { get; private set; }

    public string Name { get; private set; }

    public Machine(long id)

    {

        Id = id;

        Name = $"Machine {Id}";

    }

}

public class Task

{

    public long Id { get; private set; }

    public long MachineId { get; private set; }

    public long Duration { get; set; }

    public string Name { get; private set; }

    public Task(long jobId, long id, long machineId, long duration)

    {

        Id = id;

        MachineId = machineId;

        Duration = duration;

        Name = $"Job {jobId}; Task {id}; Machine {machineId}; Duration {duration}";

    }

}

public class Job

{

    public long Id { get; private set; }

    public List<Task> TaskList { get; private set; }

    public Job(long id)

    {

        Id = id;

        TaskList = new List<Task>();

    }

    internal void AddTask(long machineId, long duration)

    {

        Task newTask = new Task(Id, GetNewTaskId(), machineId, duration);

        TaskList.Add(newTask);

    }

    private long GetNewTaskId()

    {

        return TaskList.Count + 1;

    }

}

public class JobShop

{

    /*

    Solves the Job Shop problem

    */

    public static void Main(String[] args)

    {

        // Create example problem instance

        List<Machine> MachineList = new List<Machine> {

            new Machine(1),

            new Machine(2),

            new Machine(3)

        };

        Job j1 = new Job(1);

        Job j2 = new Job(2);

        List<Job> JobList = new List<Job> { j1, j2 };

        j1.AddTask(1, 2);

        j1.AddTask(2, 4);

        j2.AddTask(1, 3);

        j2.AddTask(2, 3);

        j2.AddTask(3, 3);

        // ----- Create all intervals and vars -----

        // Create solver

        Solver solver = new Solver("JobShop");

        long horizon = 0;

        foreach (Job job in JobList)

        {

            foreach (Task task in job.TaskList)

            {

                horizon += task.Duration;

            }

        }

        // Initialize dictionaries to hold references to task intervals

        Dictionary<long, IntervalVarVector> tasksByMachineId = new Dictionary<long, IntervalVarVector>();

        foreach (var machine in MachineList)

        {

            tasksByMachineId[machine.Id] = new IntervalVarVector();

        }

        Dictionary<long, IntervalVarVector> tasksByJobId = new Dictionary<long, IntervalVarVector>();

        foreach (var job in JobList)

        {

            tasksByJobId[job.Id] = new IntervalVarVector(job.TaskList.Count);

        }

        // Creates all individual interval variables and collect in dictionaries

        foreach (var job in JobList)

        {

            foreach (Task task in job.TaskList)

            {

                IntervalVar taskInterval = solver.MakeFixedDurationIntervalVar(0, horizon, task.Duration, false, task.Name);

                tasksByJobId[job.Id].Add(taskInterval);

                tasksByMachineId[task.MachineId].Add(taskInterval);

            }

        }

        // ----- Create model -----

        // Create precedences inside jobs

        foreach (var taskVec in tasksByJobId.Values)

        {

            for (int i = 0; i < taskVec.Count - 1; i++)

            {

                IntervalVar t1 = taskVec[i];

                IntervalVar t2 = taskVec[i + 1];

                Constraint precCt = solver.MakeIntervalVarRelation(t1, Solver.STARTS_AFTER_END, t2);

                solver.Add(precCt);

            }

        }

        // Add disjunctive constraints on unary resources, and create 

        // sequence variables. A sequence variable is a dedicated variable

        // whose job is to sequence interval variables.

        SequenceVarVector sequenceVec = new SequenceVarVector();

        foreach (var machine in MachineList)

        {

            DisjunctiveConstraint disjCt = solver.MakeDisjunctiveConstraint(tasksByMachineId[machine.Id], machine.Name);

            solver.Add(disjCt);

            sequenceVec.Add(disjCt.SequenceVar());

        }

        // Create array of end_times of jobs.

        IntVarVector endsVec = new IntVarVector();

        foreach (var taskVec in tasksByJobId.Values)

        {

            IntervalVar lastTask = taskVec[taskVec.Count - 1];

            endsVec.Add(lastTask.EndExpr().Var());

        }

        // Objective: minimize the makespan (maximum end times of all tasks)

        // of the problem.

        IntVar objectiveVar = solver.MakeMax(endsVec).Var();

        OptimizeVar objectiveMonitor = solver.MakeMinimize(objectiveVar, 1);

        // ----- Search monitors and decision builder -----

        

        // This decision builder will rank all tasks on all machines.

        DecisionBuilder sequencePhase = solver.MakePhase(

            sequenceVec, Solver.SEQUENCE_DEFAULT);

        // After the ranking of tasks, the schedule is still loose and any

        // task can be postponed at will. But, because the problem is now a PERT

        // (http://en.wikipedia.org/wiki/Program_Evaluation_and_Review_Technique),

        // we can schedule each task at its earliest start time. This is

        // conveniently done by fixing the objective variable to its

        // minimum value.

        DecisionBuilder objectivePhase = solver.MakePhase(

            objectiveVar, Solver.CHOOSE_FIRST_UNBOUND, Solver.ASSIGN_MIN_VALUE);

        // The main decision builder (ranks all tasks, then fixes the

        // objective_variable).

        DecisionBuilder mainPhase = solver.Compose(sequencePhase, objectivePhase);

        // Search log

        const int kLogFrequency = 1000000;

        SearchMonitor searchLog = solver.MakeSearchLog(kLogFrequency, objectiveMonitor);

        const long FLAGS_time_limit_in_ms = 10000;

        SearchLimit limit = null;

        if (FLAGS_time_limit_in_ms > 0)

        {

            limit = solver.MakeTimeLimit(FLAGS_time_limit_in_ms);

        }

        SolutionCollector collector = solver.MakeLastSolutionCollector();

        collector.Add(sequenceVec);

        // Search

        if (solver.Solve(mainPhase, searchLog, objectiveMonitor, limit, collector))

        {

            Console.WriteLine();

            foreach (var sequence in sequenceVec)

            {

                string msg = sequence.Name() + ": ";

                msg += string.Join(", ", collector.ForwardSequence(0, sequence));

                Console.WriteLine(msg);

            }

        }

        // Done

        Console.ReadLine();

    }

}

[Lukas Hollenstein]

Ok, after skimming the manual I realized I have to add the variables I'm interested in to the SolutionCollector object. E.g. if I want the starting times I do the following

            foreach (var taskVec in tasksByMachineId.Values)

            {

                foreach (var task in taskVec)

                {

                    collector.Add(task.StartExpr().Var());

                }

            }

before solving. Then I can access the assigned starting times of the solution like this

                    Console.Write("Starting times:");

                    foreach (var s in collector.ForwardSequence(0, sequence))

                    {

                        Console.Write(" " + collector.Value(0, tasksByMachineId[i][s].StartExpr().Var()).ToString());

                    }

                    Console.WriteLine();

where i is the index of the machine (= the index of the sequence in my sequence vector).

My question: is this the right way of doing things?

BTW, I spotted a bug in the code I posted earlier. Here's the correct version:

using System;

using System.Collections.Generic;

using Google.OrTools.ConstraintSolver;

public class Machine

public class CsJobShop

{

    /**

     * Solves the job shop problem. 

     * We have 2 machines, 2 jobs with 2 tasks each.

     */

    private static void Solve()

    {

        // Create example problem instance

        List<Machine> MachineList = new List<Machine> {

            new Machine(1),

            new Machine(2)

        };

        List<Job> JobList = new List<Job> {

            new Job(1),

            new Job(2),

            new Job(3),

            new Job(4)

        };

        long horizon = 0;

        foreach (Job job in JobList)

        {

            job.AddTask(1, 5);

            horizon += 5;

            job.AddTask(2, 4);

            horizon += 4;

        }

        // ----- Create all intervals and vars -----

        // Create solver

        Solver solver = new Solver("JobShop");

        // Initialize dictionaries to hold references to task intervals

        Dictionary<long, IntervalVarVector> tasksByJobId = new Dictionary<long, IntervalVarVector>();

        foreach (var job in JobList)

        {

            tasksByJobId[job.Id] = new IntervalVarVector(job.TaskList.Count);

        }

        Dictionary<long, IntervalVarVector> tasksByMachineId = new Dictionary<long, IntervalVarVector>();

        foreach (var machine in MachineList)

        {

            tasksByMachineId[machine.Id] = new IntervalVarVector();

        }

        // Creates all individual interval variables and collect in dictionaries

        foreach (var job in JobList)

        {

            foreach (var task in job.TaskList)

            {

                IntervalVar interval = solver.MakeFixedDurationIntervalVar(

                    0, horizon, task.Duration, false, task.Name);

                tasksByJobId[job.Id].Add(interval);

                tasksByMachineId[task.MachineId].Add(interval);

            }

        }

        // ----- Create model -----

        // Create precedences inside jobs

        foreach (var taskVec in tasksByJobId.Values)

        {

            for (int i = 0; i < taskVec.Count - 1; i++)

            {

                IntervalVar currentTask = taskVec[i];

                IntervalVar nextTask = taskVec[i + 1];

                Constraint precCt = solver.MakeIntervalVarRelation(

                    nextTask, Solver.STARTS_AFTER_END, currentTask);

        SearchLimit limit = null;

        long FLAGS_time_limit_in_ms = 1000;

        if (FLAGS_time_limit_in_ms > 0)

        {

            limit = solver.MakeTimeLimit(FLAGS_time_limit_in_ms);

        }

        SolutionCollector collector = solver.MakeLastSolutionCollector();

        collector.Add(sequenceVec);

        foreach (var taskVec in tasksByMachineId.Values)

        {

            foreach (var task in taskVec)

            {

                collector.Add(task.StartExpr().Var());

            }

        }

        // Search

        if (solver.Solve(mainPhase, searchLog, objectiveMonitor, limit, collector))

        {

            Console.WriteLine();

            int i = 0;

            foreach (var sequence in sequenceVec)

            {
                i++;

                Console.WriteLine($"{sequence.Name()}: {collector.ForwardSequence(0, sequence)}");

                Console.Write("  Starting times:");

                foreach (var s in seq)

                {

                    Console.Write(" " + collector.Value(0, tasksByMachineId[i][s].StartExpr().Var()).ToString());

                }

                Console.WriteLine();

            }

        }

    }

    public static void Main(String[] args)

    {

        Solve();

        Console.ReadLine();

    }

}