Business Objects & Instantiation
Visualization
The image below visualizes the data created above. In this example we have 4 machines "A"-"D", which can perform different tasks. These tasks are given after the name of the machine. There are 16 tasks to be done. These tasks are grouped by jobs, that means the order of the tasks in the same color must be observed over the course of time (e.g. task 2 green can not start, before task 1 green is finished). The goal is to find the optimal schedule for the tasks on the given machines while minimizing the latest end time. The latest end time is the end time of the last task, which is processed. All tasks have to finish within 40 units of time.
Task (Business Object)
Each task belongs to a certain job and is processed by a certain machine.
Task.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace JobScheduling
{
using System.Drawing;
/// <summary>
/// a task for the job scheduling problem - belongs to a job
/// </summary>
public class Task : ITask
{
/// <summary>
/// the job, this task belongs to - labeled by a color <see cref="JobScheduling.Job"/>
/// </summary>
public Job Job { get; set; }
/// <summary>
/// time step belonging to this task
/// </summary>
public int StepNumber { get; set; }
/// <summary>
/// duration of this task
/// </summary>
public int Duration { get; set; }
/// <summary>
/// a readable representation of the task
/// </summary>
/// <returns></returns>
public override string ToString()
{
return string.Format($"{this.Job}_{StepNumber-1}");
}
}
}
Job (Business Object)
The tasks of a job can be performed on various machines. Each task in job needs a certain setup time, which is determined by the job it belongs too. If there are no tasks performed before this task or the task was from the same job the setup time is zero.
Job.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace JobScheduling
{
using System.Drawing;
/// <summary>
/// A job for the job scheduling problem - consists of tasks
/// </summary>
public class Job : IJob
{
/// <summary>
/// a list of tasks for this job <see cref="JobScheduling.Task"/>
/// </summary>
public List<Task> Tasks { get; set; } = new List<Task>();
/// <summary>
/// due date of the job including all tasks
/// </summary>
public int DueDate { get; set; }
/// <summary>
/// the color is an indicator for the job
/// </summary>
public Color Color { get; set; }
/// <summary>
/// a readable representation of the job
/// </summary>
/// <returns></returns>
public override string ToString()
{
return string.Format($"{Color}").Replace(" ", "").Replace("[", "").Replace("]", "");
}
}
}
Machine (Business Object)
Each Machine is restricted to performing certain tasks. Machine.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace JobScheduling
{
using System.Drawing;
/// <summary>
/// a machine for the job scheduling problem
/// </summary>
public class Machine : IMachine
{
/// <summary>
/// label for the machine
/// </summary>
public string MachineId { get; set; }
/// <summary>
/// the tasks <see cref="JobScheduling.Task"/> that are supported by this machine
/// if a machine is assigned to a job those tasks need to match these
/// </summary>
public List<Task> SupportedTasks { get; set; } = new List<Task>();
/// <summary>
/// set-up time for the machine to do a certain job <see cref="JobScheduling.Job"/>
/// </summary>
public Dictionary<Job, int> SetupTimes {get; set;} = new Dictionary<Job, int>();
/// <summary>
/// cost for running the machine
/// </summary>
public double Cost { get; set; }
/// <summary>
/// a readable representation of the machine
/// </summary>
/// <returns></returns>
public override string ToString()
{
return MachineId;
}
}
}
Program instance
Instantiation of the different Tasks, Jobs, Machines and the Model, as well as the Solver and an empty Solution.
Program.cs
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using OPTANO.Modeling.Optimization.Solver.Gurobi810;
namespace JobScheduling
{
using System.Drawing;
using System.IO;
using OPTANO.Modeling.Common;
using OPTANO.Modeling.Optimization;
using OPTANO.Modeling.Optimization.Configuration;
using OPTANO.Modeling.Optimization.Enums;
using OPTANO.Modeling.Optimization.Solver.Cplex127;
/// <summary>
/// Program for solving the job scheduling problem
/// </summary>
class Program
{
/// <summary>
/// The main method
/// </summary>
/// <param name="args">
/// no arguments required
/// </param>
static void Main(string[] args)
{
// create jobs with their respective color and due date
var jobs = new List<Job>
{
new Job { Color = Color.White, DueDate = 40 },
new Job { Color = Color.Brown, DueDate = 40 },
new Job { Color = Color.Green, DueDate = 40 },
new Job { Color = Color.Black, DueDate = 40 },
};
// add setup times for the jobs created beforehand
var setupTimes = new Dictionary<Job, int>()
{
{ jobs.Single(j => j.Color == Color.White), 4 },
{ jobs.Single(j => j.Color == Color.Brown), 2 },
{ jobs.Single(j => j.Color == Color.Green), 3 },
{ jobs.Single(j => j.Color == Color.Black), 0 },
};
// add tasks to the different jobs created beforehand
var tasks = new List<Task>
{
// white
new Task() { Job = jobs.Single(j => j.Color == Color.White), StepNumber = 1, Duration = 4 },
new Task() { Job = jobs.Single(j => j.Color == Color.White), StepNumber = 2, Duration = 3 },
new Task() { Job = jobs.Single(j => j.Color == Color.White), StepNumber = 3, Duration = 4 },
new Task() { Job = jobs.Single(j => j.Color == Color.White), StepNumber = 4, Duration = 2 },
// brown
new Task() { Job = jobs.Single(j => j.Color == Color.Brown), StepNumber = 1, Duration = 4 },
new Task() { Job = jobs.Single(j => j.Color == Color.Brown), StepNumber = 2, Duration = 6 },
new Task() { Job = jobs.Single(j => j.Color == Color.Brown), StepNumber = 3, Duration = 4 },
new Task() { Job = jobs.Single(j => j.Color == Color.Brown), StepNumber = 4, Duration = 3 },
// green
new Task() { Job = jobs.Single(j => j.Color == Color.Green), StepNumber = 1, Duration = 3 },
new Task() { Job = jobs.Single(j => j.Color == Color.Green), StepNumber = 2, Duration = 4 },
new Task() { Job = jobs.Single(j => j.Color == Color.Green), StepNumber = 3, Duration = 3 },
new Task() { Job = jobs.Single(j => j.Color == Color.Green), StepNumber = 4, Duration = 3 },
// black
new Task() { Job = jobs.Single(j => j.Color == Color.Black), StepNumber = 1, Duration = 4 },
new Task() { Job = jobs.Single(j => j.Color == Color.Black), StepNumber = 2, Duration = 8 },
new Task() { Job = jobs.Single(j => j.Color == Color.Black), StepNumber = 3, Duration = 2 },
new Task() { Job = jobs.Single(j => j.Color == Color.Black), StepNumber = 4, Duration = 8 },
};
// create a rank for each task
var ranks = Enumerable.Range(0, tasks.Count).ToList();
// set up the machines with their name, the beforehand created setup times and the supported tasks as well as their setup cost
var machines = new List<Machine>
{
new Machine
{
MachineId = "A",
SetupTimes = setupTimes,
SupportedTasks = tasks.Where(task => new int[] { 1, 2 }.Contains(task.StepNumber)).ToList(),
Cost = 1
},
new Machine
{
MachineId = "B",
SetupTimes = setupTimes,
SupportedTasks = tasks.Where(task => new int[] { 1, 2, 3 }.Contains(task.StepNumber)).ToList(),
Cost = 2
},
new Machine
{
MachineId = "C",
SetupTimes = setupTimes,
SupportedTasks = tasks.Where(task => new int[] { 2, 3, 4 }.Contains(task.StepNumber)).ToList(),
Cost = 3
},
new Machine
{
MachineId = "D",
SetupTimes = setupTimes,
SupportedTasks = tasks.Where(task => new int[] { 3, 4 }.Contains(task.StepNumber)).ToList(),
Cost = 4
},
};
// register tasks with jobs
jobs.ForEach(job => job.Tasks.AddRange(tasks.Where(task => task.Job == job).OrderBy(task => task.StepNumber)));
// Use long names for easier debugging/model understanding.
var config = new Configuration();
config.NameHandling = NameHandlingStyle.UniqueLongNames;
config.ComputeRemovedVariables = true;
using (var scope = new ModelScope(config))
{
// create a model, based on given data and the model scope
var jobScheduleModel = new JobScheduleModel(jobs, setupTimes, tasks, ranks, machines);
// Get a solver instance, change your solver
var solverConfig = new GurobiSolverConfiguration { TimeLimit = 120 };
using (var solver = new GurobiSolver(solverConfig))
{
// solve the model
var solution = solver.Solve(jobScheduleModel.Model);
// print objective and variable decisions
Console.WriteLine(
$"Objective: {solution.ObjectiveValues.Single().Key} {(int)Math.Round(solution.ObjectiveValues.Single().Value)}");
Console.WriteLine($"Latest End: {(int)jobScheduleModel.LatestEnd.Value}");
foreach (var machine in machines)
{
foreach (var rank in ranks)
{
foreach (var task in machine.SupportedTasks)
{
if ((int)Math.Round(jobScheduleModel.taskMachineAssignment[task, machine, rank].Value) > 0)
{
Console.WriteLine(
$"Machine {machine}, Rank {rank}: Assigns Task={task}, Start: {(int)Math.Round(jobScheduleModel.startTime[task, machine, rank].Value):####}, Duration: {task.Duration:##}, End: {(int)Math.Round(jobScheduleModel.startTime[task, machine, rank].Value) + task.Duration:####}");
}
}
}
Console.WriteLine("---");
}
foreach (var job in jobs)
{
foreach (var task in job.Tasks)
{
foreach (var machine in machines.Where(m => m.SupportedTasks.Contains(task)))
{
foreach (var rank in ranks)
{
if ((int)Math.Round(jobScheduleModel.taskMachineAssignment[task, machine, rank].Value) > 0)
{
Console.WriteLine(
$"Task={task}, Rank {rank}: Assigned Machine {machine}, Start: {(int)Math.Round(jobScheduleModel.startTime[task, machine, rank].Value):####}, Duration: {task.Duration:##}, End: {(int)Math.Round(jobScheduleModel.startTime[task, machine, rank].Value) + task.Duration:####}");
}
}
}
}
Console.WriteLine("---");
}
Console.ReadLine();
}
}
}
}
}
Next Step
- Creating the Model