Resource-Constrained Parallel Machine Scheduling Problem
SchedulingProblem
In the Resource-Constrained Parallel Machine Scheduling Problem, a set of tasks must be assigned to parallel identical disjunctive machines. Sequence-dependent setup times apply between consecutive tasks on the same machine. Each task can be allocated a variable number of renewable resources. The processing time of each task is nonlinear and depends on the number of resources allocated to the task. The total resource consumption at any time must not exceed the global resource limit. The objective consists in minimizing the makespan (last completion time).
Principles learned
- Add interval decision variables to model the tasks
- Add list decision variables to model the assignment of tasks on the machines and their order
- Define lambda functions to model the disjunctive and cumulative resource constraints
Data
We provide randomly generated instances of the Resource-Constrained Parallel Machine Scheduling Problem with the following format:
- The number of parallel machines.
- The number of tasks.
- The type of each task.
- The release date of each task.
- The lower bound of the number of resources needed to perform each task.
- The upper bound of the number of resources needed to perform each task.
- The base duration for each task (then normalized by the number of assigned resources).
- The setup time matrix, which indicates the minimal transition time on a given machine between two consecutive tasks.
Program
The Hexaly model for the Resource-Constrained Parallel Machine Scheduling Problem relies on three types of decision variables:
- An array of list decisions representing the machines: list i corresponds to the sequence of tasks assigned to machine i;
- An array of interval decisions representing the time span of the tasks;
- An array of integer decisions representing the number of resources assigned to each task.
We define the constraints of the problem as follows. Each task must be assigned to exactly one machine, ensuring a unique allocation. The processing interval associated with each task must match its required duration, which depends on the number of resources assigned to it.
The disjunctive resource constraints can be formulated as follows: for all i, the task processed in position i+1 must start after the end of the task processed in position i plus the setup time between these two tasks. To model this constraint, we define a lambda function expressing the relationship between two consecutive tasks. This function is then used within a variadic and operator over all tasks processed by each machine. Note that the number of terms inside these and expressions varies during the search, along with the size of the lists (the number of tasks assigned to each machine).
The cumulative resource constraints can be formulated as follows: for each time slot t, the number of resources used by the tasks that are being processed must not exceed the total number of resources. We use a variadic and formulation with a lambda function to ensure the number of available resources is respected at any time. Thanks to this variadic and, the constraint formulation remains compact and efficient even if the time horizon is very large.
The objective function is to minimize the makespan, i.e., the last completion time.
- Execution
-
hexaly resource_constrained_parallel_scheduling.hxm inFileName=instances/instance.txt [hxTimeLimit=] [solFileName=]
/********** resource_constrained_parallel_scheduling.hxm **********/
use io;
use hexaly;
function input() {
local usage = "\nUsage: hexaly resource_constrained_parallel_scheduling.hxm "
+ "inFileName=inputFile [solFileName=outputFile] [hxTimeLimit=timeLimit]\n";
if (inFileName == nil) throw usage;
local inFile = io.openRead(inFileName);
// Number of machines
nbMachines = inFile.readInt();
// Tasks data
nbTasks = inFile.readInt();
taskTypes[_ in 0...nbTasks] = inFile.readInt();
releaseDates[_ in 0...nbTasks] = inFile.readInt();
// Resources data
nbResources = inFile.readInt();
minResources[_ in 0...nbTasks] = inFile.readInt();
maxResources[_ in 0...nbTasks] = inFile.readInt();
local maxTotalResources = max[t in maxResources](t);
// Durations data
durations[_ in 0...maxTotalResources][i in 0...nbTasks] = inFile.readInt();
// Setup times between two consecutive tasks
for [i in 0...nbTasks][j in 0...nbTasks] {
setup[i][j] = inFile.readInt();
}
inFile.close();
// Horizon: trivial upper bound for the end times of the tasks
H = max[i in 0...nbTasks](releaseDates[i])
+ sum[i in 0...nbTasks](durations[0][i]);
}
function model() {
// Interval decisions: time range of each task
tasks[i in 0...nbTasks] <- interval(releaseDates[i], H);
// Number of resources assigned to each task
nbAssignedResources[i in 0...nbTasks]
<- int(minResources[taskTypes[i]], maxResources[taskTypes[i]]);
// List decisions: sequence of tasks on each machine
tasksOrder[_ in 0...nbMachines] <- list(nbTasks);
// Each task is scheduled on a machine
constraint partition(tasksOrder);
// Non-overlap constraints: the tasks assigned to the same machine are
// scheduled one after the other, with sequence-dependent setup times
for [m in 0...nbMachines] {
local sequence <- tasksOrder[m];
constraint and(0...count(sequence)-1, i => end(tasks[sequence[i]])
+ setup[sequence[i]][sequence[i+1]] <= start(tasks[sequence[i+1]]));
}
// The task duration depends on the number of assigned resources
for [i in 0...nbTasks] {
constraint length(tasks[i]) == durations[nbAssignedResources[i]-1][i];
}
// Makespan: time when all tasks have been processed
makespan <- max[i in 0...nbTasks](end(tasks[i]));
// Cumulative constraint: the number of assigned resources at any time
// does not exceed the total number of available resources
constraint and(0...makespan, t => sum[i in 0...nbTasks](
contains(tasks[i], t) * nbAssignedResources[i]) <= nbResources);
// Minimize the makespan
minimize makespan;
}
function param() {
if (hxTimeLimit is nil) hxTimeLimit = 60;
}
function output() {
if (solFileName == nil) return;
local outfile = io.openWrite(solFileName);
/* Write the solution in a file with the following format:
* - the total makespan
* - for each task, the machine, the start and end times,
* the number of assigned resources */
outfile.println(makespan.value);
for [m in 0...nbMachines] {
for [i in tasksOrder[m].value] {
outfile.print(
m, " ",
tasks[i].value.start, " ",
tasks[i].value.end, " ",
nbAssignedResources[i].value
);
outfile.println();
}
}
println("Solution written in " + solFileName);
}
- Execution (Windows)
-
set PYTHONPATH=%HX_HOME%\bin\pythonpython resource_constrained_parallel_scheduling.py instances\instance.txt
- Execution (Linux)
-
export PYTHONPATH=/opt/hexaly_14_5/bin/pythonpython resource_constrained_parallel_scheduling.py instances/instance.txt
import hexaly.optimizer
import sys
import math
def main(instance_file, output_file, time_limit):
with hexaly.optimizer.HexalyOptimizer() as optimizer:
#
# Declare the optimization model
#
model = optimizer.model
with open(instance_file) as f:
lines = f.readlines()
# Number of resources
nb_machines = int(lines[0])
# Tasks data
nb_tasks = int(lines[1])
task_types = [int(i) for i in lines[2].split()]
release_dates = [int(i) for i in lines[3].split()]
# Resources data
nb_resources = int(lines[4])
min_resources = [int(i) for i in lines[5].split()]
max_resources = [int(i) for i in lines[6].split()]
# Durations data
durations = []
for line in lines[7:12]:
line_split = [int(i) for i in line.split()]
durations.append(line_split)
# Setup times between two consecutive tasks
setup = []
for line in lines[12:]:
line_split = [int(i) for i in line.split()]
setup.append(line_split)
setup = model.array(setup)
# Horizon: trivial upper bound for the end times of the tasks
H = max(release_dates) + sum(durations[0])
# Interval decisions: time range of each task
tasks = model.array([model.interval(release_dates[i], H) for i in range(nb_tasks)])
# Number of resources assigned to each task
nb_assigned_resources = model.array( \
[model.int(min_resources[task_types[i]], max_resources[task_types[i]]) \
for i in range(nb_tasks)])
# List decisions: sequence of tasks on each machine
tasks_order = model.array([model.list(nb_tasks) for _ in range(nb_machines)])
# Each task is scheduled on a machine
model.constraint(model.partition(tasks_order))
# Non-overlap constraints: the tasks assigned to the same machine are
# scheduled one after the other, with sequence-dependent setup times
for m in range(nb_machines):
sequence = tasks_order[m]
no_overlap_lambda = model.lambda_function(
lambda i : model.end(tasks[sequence[i]]) + setup[sequence[i]][sequence[i+1]] \
<= model.start(tasks[sequence[i+1]]))
model.constraint(model.and_( \
model.range(0, model.count(sequence)-1), no_overlap_lambda))
# The task duration depends on the number of assigned resources
durations = model.array(durations)
for i in range(nb_tasks):
model.constraint(model.length(tasks[i]) == durations[nb_assigned_resources[i]-1][i])
# Makespan: time when all tasks have been processed
makespan = model.max([model.end(tasks[i]) \
for i in range(nb_tasks)])
# Cumulative constraint: the number of assigned resources at any time
# does not exceed the total number of available resources
capacity_lambda = model.lambda_function(
lambda t : model.sum(model.contains(tasks[i], t) \
* nb_assigned_resources[i] for i in range(0, nb_tasks)) \
<= nb_resources
)
model.constraint(model.and_(model.range(0, makespan), capacity_lambda))
# Minimize the makespan
model.minimize(makespan)
model.close()
# Parameterize the optimizer
optimizer.param.time_limit = time_limit
optimizer.solve()
# Write the solution in a file with the following format:
# - the total makespan
# - for each task, the machine, the start and end times,
# the number of assigned resources */
if output_file != None:
with open(output_file, "w") as f:
f.write(str(makespan.value))
f.write("\n")
for m in range(nb_machines):
for i in tasks_order.value[m]:
f.write(str(m) + " " \
+ str(tasks.value[i].start()) + " " \
+ str(tasks.value[i].end()) + " " \
+ str(nb_assigned_resources.value[i]))
f.write("\n")
print("Solution written in file ", output_file)
if __name__ == '__main__':
if len(sys.argv) < 2:
print("Usage: python resource_constrained_parallel_scheduling.py" \
"instance_file [output_file] [time_limit]")
sys.exit(1)
instance_file = sys.argv[1]
output_file = sys.argv[2] if len(sys.argv) >= 3 else None
time_limit = int(sys.argv[3]) if len(sys.argv) >= 4 else 60
main(instance_file, output_file, time_limit)
- Compilation / Execution (Windows)
-
cl /EHsc resource_constrained_parallel_scheduling.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly145.libresource_constrained_parallel_scheduling instances\instance.txt
- Compilation / Execution (Linux)
-
g++ resource_constrained_parallel_scheduling.cpp -I/opt/hexaly_14_5/include -lhexaly145 -lpthread -o resource_constrained_parallel_scheduling./resource_constrained_parallel_scheduling instances/instance.txt
#include "optimizer/hexalyoptimizer.h"
#include <fstream>
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <cmath>
using namespace hexaly;
using namespace std;
class ResourceConstrainedParallelScheduling {
private:
// Number of machines
int nbMachines;
// Tasks data
int nbTasks;
vector<int> taskTypes;
vector<int> releaseDates;
// Resources data
int nbResources;
vector<int> minResources;
vector<int> maxResources;
int maxTotalResources;
// Durations data
vector<vector<int>> durationsData;
// Setup times between two consecutive tasks
vector<vector<int>> setupData;
// Horizon: trivial upper bound for the end times of the tasks
int H;
// Hexaly Optimizer
HexalyOptimizer optimizer;
vector<HxExpression> tasks;
vector<HxExpression> nbAssignedResources;
vector<HxExpression> tasksOrder;
HxExpression makespan;
public:
void readInstance(const string& inFileName);
void solve(int timeLimit);
void writeSolution(const string& fileName);
};
void ResourceConstrainedParallelScheduling::readInstance(const string& inFileName) {
ifstream infile;
infile.exceptions(ifstream::failbit | ifstream::badbit);
infile.open(inFileName.c_str());
infile >> nbMachines;
infile >> nbTasks;
int value;
for (int i = 0; i < nbTasks; ++i) {
infile >> value;
taskTypes.push_back(value);
}
for (int i = 0; i < nbTasks; ++i) {
infile >> value;
releaseDates.push_back(value);
}
infile >> nbResources;
for (int i = 0; i < nbTasks; ++i) {
infile >> value;
minResources.push_back(value);
}
for (int i = 0; i < nbTasks; ++i) {
infile >> value;
maxResources.push_back(value);
}
maxTotalResources = *max_element(maxResources.begin(), maxResources.end());
for (unsigned int m = 0; m < maxTotalResources; m++) {
durationsData.push_back(vector<int> {});
for (unsigned int i = 0; i < nbTasks; i++) {
infile >> value;
durationsData[m].push_back(value);
}
}
for (int i = 0; i < nbTasks; ++i) {
setupData.push_back(vector<int> {});
for (int j = 0; j < nbTasks; ++j) {
infile >> value;
setupData[i].push_back(value);
}
}
H = *max_element(releaseDates.begin(), releaseDates.end())
+ accumulate(durationsData[0].begin(), durationsData[0].end(), 0);
infile.close();
}
void ResourceConstrainedParallelScheduling::solve(int timeLimit) {
// Declare the optimization model
HxModel model = optimizer.getModel();
// Interval decisions: time range of each task
for (int i = 0; i < nbTasks; ++i) {
tasks.push_back(model.intervalVar(releaseDates[i], H));
}
HxExpression tasksArray = model.array(tasks.begin(), tasks.end());
// Number of resources assigned to each task
for (int i = 0; i < nbTasks; i++) {
nbAssignedResources.push_back(
model.intVar(minResources[taskTypes[i]],
maxResources[taskTypes[i]]));
}
HxExpression nbAssignedResourcesArray
= model.array(nbAssignedResources.begin(), nbAssignedResources.end());
// List decisions: sequence of tasks on each machine
for (int m = 0; m < nbMachines; ++m)
tasksOrder.push_back(model.listVar(nbTasks));
// Each task is scheduled on a machine
model.constraint(model.partition(tasksOrder.begin(), tasksOrder.end()));
// Non-overlap constraints: the tasks assigned to the same machine are
// scheduled one after the other, with sequence-dependent setup times
HxExpression setup = model.array();
for (int i = 0; i < nbTasks; ++i) {
setup.addOperand(
model.array(setupData[i].begin(), setupData[i].end())
);
}
for (int m = 0; m < nbMachines; m++) {
HxExpression sequence = tasksOrder[m];
HxExpression noOverlapLambda = model.lambdaFunction([&](HxExpression i) {
return (model.end(tasksArray[sequence[i]])
+ setup[sequence[i]][sequence[i+1]]
<= model.start(tasksArray[sequence[i+1]]));
});
model.constraint(model.and_(model.range(0, model.count(sequence)-1), noOverlapLambda));
}
// The task duration depends on the number of assigned resources
HxExpression durations = model.array();
for (int r = 0; r < maxTotalResources; ++r) {
durations.addOperand(
model.array(durationsData[r].begin(), durationsData[r].end())
);
}
for (int i = 0; i < nbTasks; i++) {
model.constraint(model.length(tasks[i]) == durations[nbAssignedResources[i]-1][i]);
}
// Makespan: time when all tasks have been processed
makespan = model.max();
for (int i = 0; i < nbTasks; ++i)
makespan.addOperand(model.end(tasks[i]));
// Cumulative constraint: the number of assigned resources at any time
// does not exceed the total number of available resources
HxExpression capacityLambda = model.lambdaFunction([&](HxExpression t) {
HxExpression curNbResources = model.sum();
for (int i = 0; i < nbTasks; i++) {
curNbResources.addOperand(model.contains(tasksArray[i], t)
* nbAssignedResourcesArray[i]);
}
return curNbResources <= nbResources;
});
model.constraint(model.and_(model.range(0, makespan), capacityLambda));
// Minimize the makespan
model.minimize(makespan);
model.close();
// Parameterize the optimizer
optimizer.getParam().setTimeLimit(timeLimit);
optimizer.solve();
}
/* Write the solution in a file with the following format:
* - the total makespan
* - for each task, the machine, the start and end times,
* the number of assigned resources */
void ResourceConstrainedParallelScheduling::writeSolution(const string& fileName) {
ofstream outfile;
outfile.exceptions(ofstream::failbit | ofstream::badbit);
outfile.open(fileName.c_str());
outfile << makespan.getValue() << endl;
for (int m = 0; m < nbMachines; ++m) {
HxCollection sequence = tasksOrder[m].getCollectionValue();
for (int i = 0; i < sequence.count(); ++i) {
outfile << m << " "
<< tasks[sequence[i]].getIntervalValue().getStart() << " "
<< tasks[sequence[i]].getIntervalValue().getEnd() <<" "
<< nbAssignedResources[sequence[i]].getIntValue() << endl;
}
}
std::cout << "Solution written in " << fileName << std::endl;
}
int main(int argc, char** argv) {
if (argc < 2) {
std::cout << "Usage: resource_constrained_parallel_scheduling"
<< " instanceFile [outputFile] [timeLimit]" << std::endl;
exit(1);
}
const char* instanceFile = argv[1];
string inFileName = string(instanceFile);
const char* outputFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "60";
try {
ResourceConstrainedParallelScheduling model;
model.readInstance(inFileName);
int TimeLimit = atoi(strTimeLimit);
model.solve(TimeLimit);
if (outputFile != NULL) {
model.writeSolution(outputFile);
}
return 0;
} catch (const std::exception& e) {
std::cerr << "An error occurred: " << e.what() << std::endl;
return 1;
}
}
- Compilation / Execution (Windows)
-
copy %HX_HOME%\bin\Hexaly.NET.dll .csc ResourceConstrainedParallelScheduling.cs /reference:Hexaly.NET.dllResourceConstrainedParallelScheduling instances\instance.txt
using System;
using System.IO;
using System.Linq;
using Hexaly.Optimizer;
using System.Collections.Generic;
public class ResourceConstrainedParallelScheduling : IDisposable
{
// Number of machines
private int nbMachines;
// Tasks data
private int nbTasks;
private int[] taskTypes;
private int[] releaseDates;
// Resources data
private int nbResources;
private int[] minResources;
private int[] maxResources;
// Durations data
private int[,] durationsData;
// Setup times between two consecutive tasks
private int[,] setupData;
// Horizon: trivial upper bound for the end times of the tasks
private int H;
// Hexaly Optimizer
private HexalyOptimizer optimizer;
private HxExpression[] tasks;
private HxExpression[] nbAssignedResources;
private HxExpression[] tasksOrder;
private HxExpression makespan;
public ResourceConstrainedParallelScheduling()
{
optimizer = new HexalyOptimizer();
}
public void ReadInstance(string fileName)
{
using (StreamReader input = new StreamReader(fileName))
{
nbMachines = int.Parse(input.ReadLine());
nbTasks = int.Parse(input.ReadLine());
string[] line_sp = input.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);
taskTypes = Array.ConvertAll(line_sp, int.Parse);
line_sp = input.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);
releaseDates = Array.ConvertAll(line_sp, int.Parse);
nbResources = int.Parse(input.ReadLine());
line_sp = input.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);
minResources = Array.ConvertAll(line_sp, int.Parse);
line_sp = input.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);
maxResources = Array.ConvertAll(line_sp, int.Parse);
int maxTotalResources = maxResources.Max();
durationsData = new int[maxTotalResources, nbTasks];
for (int i = 0; i < maxTotalResources; ++i)
{
line_sp = input.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries);
int[] lineDuration = Array.ConvertAll(line_sp, int.Parse);
for (int j = 0; j < nbTasks; ++j) durationsData[i, j] = lineDuration[j];
}
int baseLineDurationSum = 0;
for (int i = 0; i < nbTasks; ++i) baseLineDurationSum += durationsData[0, i];
H = releaseDates.Max() + baseLineDurationSum;
List<int[]> setupMatrixTemp = new List<int[]>();
string line;
while ((line = input.ReadLine()) != null)
{
string[] valuesStr = line.Split(new char[] { ' ', '\t' },
StringSplitOptions.RemoveEmptyEntries);
int[] values = Array.ConvertAll(valuesStr, int.Parse);
setupMatrixTemp.Add(values);
}
int nbLines = setupMatrixTemp.Count;
setupData = new int[nbLines, nbLines];
for (int i = 0; i < nbLines; ++i)
{
for (int j = 0; j < nbLines; ++j) setupData[i, j] = setupMatrixTemp[i][j];
}
}
}
public void Dispose()
{
optimizer.Dispose();
}
public void Solve(int timeLimit)
{
// Declare the optimization model
HxModel model = optimizer.GetModel();
// Interval decisions: time range of each task
tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i)
{
tasks[i] = model.Interval(releaseDates[i], H);
}
HxExpression tasksArray = model.Array(tasks);
// Number of resources assigned to each task
nbAssignedResources = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i)
{
nbAssignedResources[i] = model.Int(minResources[taskTypes[i]],
maxResources[taskTypes[i]]);
}
HxExpression nbAssignedResourcesArray = model.Array(nbAssignedResources);
// List decisions: sequence of tasks on each machine
tasksOrder = new HxExpression[nbMachines];
for (int i = 0; i < nbMachines; ++i) tasksOrder[i] = model.List(nbTasks);
// Each task is scheduled on a machine
HxExpression tasksOrderArray = model.Array(tasksOrder);
model.Constraint(model.Partition(tasksOrderArray));
// Non-overlap constraints: the tasks assigned to the same machine are
// scheduled one after the other, with sequence-dependent setup times
HxExpression setup = model.Array(setupData);
for (int m = 0; m < nbMachines; ++m)
{
HxExpression sequence = tasksOrder[m];
HxExpression noOverlapLambda = model.LambdaFunction(i =>
model.End(tasksArray[sequence[i]]) + setup[sequence[i]][sequence[i+1]]
<= model.Start(tasksArray[sequence[i+1]])
);
model.Constraint(model.And(model.Range(0, model.Count(sequence)-1), noOverlapLambda));
}
// The task duration depends on the number of assigned resources
HxExpression durations = model.Array(durationsData);
for (int i = 0; i < nbTasks; ++i)
{
model.Constraint(model.Length(tasks[i])
== durations[nbAssignedResources[i]-1][i]);
}
// Makespan: time when all tasks have been processed
makespan = model.Max();
for (int i = 0; i < nbTasks; ++i) makespan.AddOperand(model.End(tasks[i]));
// Cumulative constraint: the number of assigned resources at any time
// does not exceed the total number of available resources
HxExpression capacityLambda = model.LambdaFunction(t =>
{
HxExpression curNbResources = model.Sum();
for (int i = 0; i < nbTasks; i++)
{
curNbResources.AddOperand(model.Contains(tasksArray[i], t)
* nbAssignedResourcesArray[i]
);
}
return curNbResources <= nbResources;
});
model.Constraint(model.And(model.Range(0, makespan), capacityLambda));
// Minimize the makespan
model.Minimize(makespan);
model.Close();
// Parameterize the optimizer
optimizer.GetParam().SetTimeLimit(timeLimit);
optimizer.Solve();
}
/* Write the solution in a file with the following format:
* - the total makespan
* - for each task, the machine, the start and end times,
* the number of assigned resources */
public void WriteSolution(string fileName)
{
using (StreamWriter output = new StreamWriter(fileName))
{
output.Write(makespan.GetValue());
output.WriteLine();
for (int m = 0; m < nbMachines; ++m)
{
HxCollection sequence = tasksOrder[m].GetCollectionValue();
for (int i = 0; i < sequence.Count(); ++i)
{
output.Write(m + " "
+ tasks[sequence[i]].GetIntervalValue().Start() + " "
+ tasks[sequence[i]].GetIntervalValue().End() + " "
+ nbAssignedResources[sequence[i]].GetIntValue());
output.WriteLine();
}
}
Console.WriteLine("Solution written in file " + fileName);
}
}
public static void Main(string[] args)
{
if (args.Length < 1)
{
Console.WriteLine("Usage: ResourceConstrainedParallelScheduling instanceFile [outputFile] [timeLimit]");
System.Environment.Exit(1);
}
string instanceFile = args[0];
string outputFile = args.Length > 1 ? args[1] : null;
string strTimeLimit = args.Length > 2 ? args[2] : "60";
using (ResourceConstrainedParallelScheduling model = new ResourceConstrainedParallelScheduling())
{
model.ReadInstance(instanceFile);
model.Solve(int.Parse(strTimeLimit));
if (outputFile != null) model.WriteSolution(outputFile);
}
}
}
- Compilation / Execution (Windows)
-
javac ResourceConstrainedParallelScheduling.java -cp %HX_HOME%\bin\hexaly.jarjava -cp %HX_HOME%\bin\hexaly.jar;. ResourceConstrainedParallelScheduling instances\instance.txt
- Compilation / Execution (Linux)
-
javac ResourceConstrainedParallelScheduling.java -cp /opt/hexaly_14_5/bin/hexaly.jarjava -cp /opt/hexaly_14_5/bin/hexaly.jar:. ResourceConstrainedParallelScheduling instances/instance.txt
import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;
public class ResourceConstrainedParallelScheduling {
// Number of machines
private int nbMachines;
// Tasks data
private int nbTasks;
private int[] taskTypes;
private int[] releaseDates;
// Resources data
private int nbResources;
private int[] minResources;
private int[] maxResources;
// Durations data
private int[][] durationsData;
// Setup times between two consecutive tasks
private int[][] setupData;
// Horizon: trivial upper bound for the end times of the tasks
private int H;
// Hexaly Optimizer
final HexalyOptimizer optimizer;
private HxExpression[] tasks;
private HxExpression[] nbAssignedResources;
private HxExpression[] tasksOrder;
private HxExpression makespan;
public ResourceConstrainedParallelScheduling(HexalyOptimizer optimizer) throws IOException {
this.optimizer = optimizer;
}
public static int maxInt(int[] v) {
return Arrays.stream(v).max().getAsInt();
}
public void readInstance(String fileName) throws IOException {
try (Scanner input = new Scanner(new File(fileName))) {
input.useLocale(Locale.ROOT);
nbMachines = input.nextInt();
nbTasks = input.nextInt();
taskTypes = new int[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
taskTypes[i] = input.nextInt();
}
releaseDates = new int[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
releaseDates[i] = input.nextInt();
}
nbResources = input.nextInt();
minResources = new int[nbTasks];
for (int i = 0; i < nbTasks; ++i) minResources[i] = input.nextInt();
maxResources = new int[nbTasks];
for (int i = 0; i < nbTasks; ++i) maxResources[i] = input.nextInt();
int maxTotalResources = maxInt(maxResources);
durationsData = new int[maxTotalResources][nbTasks];
for (int r = 0; r < maxTotalResources; ++r) {
for (int i = 0; i < nbTasks; ++i) {
durationsData[r][i] = input.nextInt();
}
}
H = maxInt(releaseDates) + Arrays.stream(durationsData[0]).sum();
setupData = new int[nbTasks][nbTasks];
for (int i = 0; i < nbTasks; ++i) {
int[] col = new int[nbTasks];
for (int j = 0; j < nbTasks; ++j) col[j] = (input.nextInt());
setupData[i] = col;
}
}
}
public void solve(int timeLimit) {
// Declare the optimization model
HxModel model = optimizer.getModel();
// Interval decisions: time range of each task
tasks = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
tasks[i] = model.intervalVar(releaseDates[i], H);
}
HxExpression tasksArray = model.array(tasks);
// Number of resources assigned to each task
nbAssignedResources = new HxExpression[nbTasks];
for (int i = 0; i < nbTasks; ++i) {
nbAssignedResources[i] = model.intVar(
minResources[taskTypes[i]], maxResources[taskTypes[i]]);
}
HxExpression nbAssignedResourcesArray = model.array(nbAssignedResources);
// List decisions: sequence of tasks on each machine
tasksOrder = new HxExpression[nbMachines];
for (int i = 0; i < nbMachines; ++i) tasksOrder[i] = model.listVar(nbTasks);
// Each task is scheduled on a machine
HxExpression tasksOrderArray = model.array(tasksOrder);
model.constraint(model.partition(tasksOrderArray));
// Non-overlap constraints: the tasks assigned to the same machine are
// scheduled one after the other, with sequence-dependent setup times
HxExpression setup = model.array(setupData);
for (int m = 0; m < nbMachines; ++m) {
HxExpression sequence = tasksOrder[m];
HxExpression noOverlapLambda = model.lambdaFunction(i -> {
return model.leq(
model.sum(
model.end(model.at(tasksArray, model.at(sequence,i))),
model.at(setup, model.at(sequence, i), model.at(sequence, model.sum(i, 1)))
),
model.start(model.at(tasksArray, model.at(sequence, model.sum(i, 1))))
);
});
model.constraint(model.and(
model.range(0, model.sum(model.count(sequence), -1)), noOverlapLambda));
}
// The task duration depends on the number of assigned resources
HxExpression durations = model.array(durationsData);
for (int i = 0; i < nbTasks; ++i) {
model.constraint(model.eq(model.length(tasks[i]),
model.at(model.at(durations, model.sum(nbAssignedResources[i], -1)), i)));
}
// Makespan: time when all tasks have been processed
makespan = model.max();
for (int i = 0; i < nbTasks; ++i) makespan.addOperand(model.end(tasks[i]));
// Cumulative constraint: the number of assigned resources at any time
// does not exceed the total number of available resources
HxExpression capacityLambda = model.lambdaFunction(t -> {
HxExpression curNbResources = model.sum();
for (int i = 0; i < nbTasks; i++) {
curNbResources.addOperand(model.prod(model.contains(model.at(tasksArray, i), t),
model.at(nbAssignedResourcesArray, i)));
}
return model.leq(curNbResources, nbResources);
}
);
model.constraint(model.and(model.range(0, makespan), capacityLambda));
// Minimize the makespan
model.minimize(makespan);
model.close();
// Parameterize the optimizer
optimizer.getParam().setTimeLimit(timeLimit);
optimizer.solve();
}
/* Write the solution in a file with the following format:
* - the total makespan
* - for each task, the machine, the start and end times,
* the number of assigned resources */
public void writeSolution(String fileName) throws IOException {
try (PrintWriter output = new PrintWriter(fileName)) {
output.write(makespan.getIntValue() + "\n");
for (int m = 0; m < nbMachines; ++m) {
HxCollection sequence = tasksOrder[m].getCollectionValue();
for (int idx = 0; idx < sequence.count(); ++idx) {
int i = (int)sequence.get(idx);
output.write(m + " "
+ tasks[i].getIntervalValue().getStart() + " "
+ tasks[i].getIntervalValue().getEnd() + " "
+ nbAssignedResources[i].getIntValue());
output.write("\n");
}
}
System.out.println("Solution written in file " + fileName);
}
}
public static void main(String[] args) {
if (args.length < 1) {
System.out.println("Usage: ResourceConstrainedParallelScheduling instanceFile [outputFile] [timeLimit]");
System.exit(1);
}
String instanceFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "60";
try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
ResourceConstrainedParallelScheduling model = new ResourceConstrainedParallelScheduling(optimizer);
model.readInstance(instanceFile);
model.solve(Integer.parseInt(strTimeLimit));
if (outputFile != null) model.writeSolution(outputFile);
} catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}