Oven Scheduling Problem (OSP)
SchedulingProblem
In the Oven Scheduling Problem (OSP), a set of jobs must be assigned to ovens, grouped into batches, and scheduled over a finite time horizon. Each job has a release date, a due date, a size, a processing time range, and an attribute. Each oven has an initial attribute, a capacity, and availability windows.
Jobs in the same batch must share the same attribute. In addition, consecutive batches on the same oven may require setup times and setup costs that depend on their attributes.
The objective is to minimize a weighted sum of four criteria: the total processing time of used batches, the number of tardy jobs, the setup costs and the setup times.
Principles learned
- Use set decision variables to model the contents of batches
- Use lambda functions and step arrays to model availability windows
- Use the ’distinct’ operator and a lambda function to ensure all jobs within the same batch have the same type
Data
We provide OSP input files based on the instances available in the osp-ls repository, with an adapted format to simplify model input.
Each instance contains:
- The scheduling horizon
- The number of attributes
- The setup cost matrix
- The setup time matrix
- The number of ovens
- The minimum and maximum capacity of each oven
- The initial attribute of each oven
- The availability windows of each oven
- The number of jobs
- The eligible ovens for each job
- The release date and due date of each job
- The minimum and maximum processing time of each job
- The size and attribute of each job
- The objective weights
The input only provides setup values for real destination attributes, starting at 1. By contrast, attribute 0 corresponds to empty batches. As a result, transitions to empty batches have zero setup time and zero setup cost.
Model
The Hexaly model for the Oven Scheduling Problem (OSP) uses set and interval decision variables. For each oven, it creates a fixed number of potential batches. Batch variables are stored in a flat list and then viewed as a two-dimensional structure by oven and batch position, which makes sequencing, setup, and capacity constraints easier to express.
Each batch has a set variable for the jobs assigned to it and an interval variable for its processing time. The set variables form a partition, to ensure we assign each job to exactly one batch. The find operator is used to identify the batch of each job and link it to the corresponding interval.
For each batch, the model computes its total size and attribute. The batch size cannot exceed the oven capacity, all jobs in a batch must share the same attribute, and each job can only be assigned to an eligible oven.
On each oven, consecutive batches must respect sequence-dependent setup times. Empty batches are placed after non-empty ones.
Oven availability is represented by step arrays (const arrays also work) built from availability windows. For each used batch, both setup and processing must fit within an available time period.
The objective is the weighted sum of the total processing time of used batches, the number of tardy jobs, the setup costs and the setup times.
- Execution
-
hexaly oven_scheduling_problem.hxm inFileName=instances/21-n25-k2-a2.dat [hxTimeLimit=] [solFileName=]
// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
use io;
/* Read instance data */
function input() {
local usage =
"Usage: hexaly oven_scheduling_problem.hxm "
+ "inFileName=inputFile [solFileName=outputFile] [hxTimeLimit=timeLimit]";
if (inFileName == nil) throw usage;
readData();
preprocessData();
}
/* Read instance data from the input file */
function readData() {
local inFile = io.openRead(inFileName);
horizon = inFile.readInt();
nbAttributes = inFile.readInt();
// Attribute 0 is reserved for empty batches
emptyAttribute = 0;
// Input only provides setup values for real destination attributes;
// transitions to empty batches are set to zero
setupCostsMatrix[a1 in 0...(nbAttributes + 1)][a2 in 0...(nbAttributes + 1)] =
a2 == emptyAttribute ? 0 : inFile.readInt();
setupTimesMatrix[a1 in 0...(nbAttributes + 1)][a2 in 0...(nbAttributes + 1)] =
a2 == emptyAttribute ? 0 : inFile.readInt();
nbMachines = inFile.readInt();
machineMinCapacity[m in 0...nbMachines] = inFile.readInt();
machineMaxCapacity[m in 0...nbMachines] = inFile.readInt();
machineInitialAttribute[m in 0...nbMachines] = inFile.readInt();
nbAvailabilities = inFile.readInt();
availabilityStart[m in 0...nbMachines][a in 0...nbAvailabilities] =
inFile.readInt();
availabilityEnd[m in 0...nbMachines][a in 0...nbAvailabilities] =
inFile.readInt();
nbJobs = inFile.readInt();
machineEligibility[j in 0...nbJobs][m in 0...nbMachines] = false;
for [j in 0...nbJobs] {
local nbEligible = inFile.readInt();
for [_ in 0...nbEligible] {
local machineId = inFile.readInt();
// The machine IDs in the input start at 1
machineEligibility[j][machineId - 1] = true;
}
}
jobReleaseDate[j in 0...nbJobs] = inFile.readInt();
jobDueDate[j in 0...nbJobs] = inFile.readInt();
jobMinProcessingTime[j in 0...nbJobs] = inFile.readInt();
jobMaxProcessingTime[j in 0...nbJobs] = inFile.readInt();
jobSize[j in 0...nbJobs] = inFile.readInt();
jobAttribute[j in 0...nbJobs] = inFile.readInt();
upperBoundIntegerObjective = inFile.readInt();
weightBatchProcessingTime = inFile.readInt();
weightTardyJobs = inFile.readInt();
weightSetupTimes = inFile.readInt();
weightSetupCosts = inFile.readInt();
inFile.close();
}
/* Preprocess instance data */
function preprocessData() {
// Create availability arrays from availability windows
availabilitiesDense[m in 0...nbMachines][t in 0...horizon] = 0;
for [m in 0...nbMachines][a in 0...nbAvailabilities] {
availabilitiesDense[m][availabilityStart[m][a]...availabilityEnd[m][a]] = 1;
}
// Convert availability arrays into step arrays to save space
availabilities[m in 0...nbMachines] <-
createStepArray(availabilitiesDense[m], horizon);
// Worst case: one job per batch and per machine
nbMaxBatch = nbJobs;
nbTotalBatch = nbMachines * nbMaxBatch;
}
/* Create a step array from a dense array */
function createStepArray(denseArray, horizon) {
local indexes = {};
local values = {};
local value = denseArray[0];
for [t in 1...horizon] {
if (denseArray[t] != value) {
indexes.add(t);
values.add(value);
value = denseArray[t];
}
}
indexes.add(horizon);
values.add(value);
return stepArray(indexes, values);
}
/* Declare the optimization model */
function model() {
// Set decisions: jobs assigned to each batch
batchContent[b in 0...nbTotalBatch] <- set(nbJobs);
// Interval decisions: time range of each batch
batchInterval[b in 0...nbTotalBatch] <- interval(0, horizon);
// Each job must be assigned to exactly one batch
constraint partition(batchContent);
// View batches by machine and batch position
machineBatchContent[m in 0...nbMachines][b in 0...nbMaxBatch] <-
batchContent[m * nbMaxBatch + b];
// View time ranges by machine and batch position
machineBatchInterval[m in 0...nbMachines][b in 0...nbMaxBatch] <-
batchInterval[m * nbMaxBatch + b];
// Total size of each batch
machineBatchSize[m in 0...nbMachines][b in 0...nbMaxBatch] <-
sum(machineBatchContent[m][b], (j) => jobSize[j]);
// Identify non-empty batches
machineBatchUsed[m in 0...nbMachines][b in 0...nbMaxBatch] <-
count(machineBatchContent[m][b]) > 0;
// Identify common attribute of each batch
machineBatchType[m in 0...nbMachines][b in 0...nbMaxBatch] <-
machineBatchUsed[m][b]
? min(machineBatchContent[m][b], (j) => jobAttribute[j])
: emptyAttribute;
// Batch selected for each job
jobIndex[j in 0...nbJobs] <- find(batchContent, j);
// Jobs in the same batch share the same time range
jobInterval[j in 0...nbJobs] <- batchInterval[jobIndex[j]];
for [j in 0...nbJobs] {
// Jobs cannot start before their release date
constraint start(jobInterval[j]) >= jobReleaseDate[j];
// Batch length must satisfy each assigned job
constraint length(jobInterval[j]) >= jobMinProcessingTime[j];
constraint length(jobInterval[j]) <= jobMaxProcessingTime[j];
}
for [j in 0...nbJobs]
[m in 0...nbMachines : !machineEligibility[j][m]]
[b in 0...nbMaxBatch] {
// Jobs can only be assigned to eligible machines
constraint !contains(machineBatchContent[m][b], j);
}
for [b in 0...nbTotalBatch] {
// Each batch must consist of jobs with the same type
constraint (
count(distinct(batchContent[b], (j) => jobAttribute[j])) <= 1
);
}
for [m in 0...nbMachines][b in 0...nbMaxBatch] {
// Batch size cannot exceed the machine capacity
constraint machineBatchSize[m][b] <= machineMaxCapacity[m];
}
for [m in 0...nbMachines][b in 1...nbMaxBatch] {
local prevAttribute <- machineBatchType[m][b - 1];
local nextAttribute <- machineBatchType[m][b];
local setupTime <- setupTimesMatrix[prevAttribute][nextAttribute];
// Non-overlap between batches, with sequence-dependent setup times
constraint (
end(machineBatchInterval[m][b - 1]) + setupTime
<= start(machineBatchInterval[m][b])
);
// Empty batches must be last to keep setups between non-empty batches
constraint machineBatchUsed[m][b - 1] >= machineBatchUsed[m][b];
}
for [m in 0...nbMachines] {
local setupTime <- setupTimesMatrix[machineInitialAttribute[m]]
[machineBatchType[m][0]];
// Account for the setup time before the first batch for each machine
constraint start(machineBatchInterval[m][0]) >= setupTime;
}
// Setup costs between each batch
machineSetupCosts[m in 0...nbMachines] <-
sum(
1...nbMaxBatch,
(b) => {
local prevAttribute <- machineBatchType[m][b - 1];
local nextAttribute <- machineBatchType[m][b];
return setupCostsMatrix[prevAttribute][nextAttribute];
}
);
// Setup times between each batch
machineSetupTimes[m in 0...nbMachines] <-
sum(
1...nbMaxBatch,
(b) => {
local prevAttribute <- machineBatchType[m][b - 1];
local nextAttribute <- machineBatchType[m][b];
return setupTimesMatrix[prevAttribute][nextAttribute];
}
);
for [m in 0...nbMachines][b in 0...nbMaxBatch] {
local nextInterval <- machineBatchInterval[m][b];
local prevAttribute <- b == 0 ? emptyAttribute : machineBatchType[m][b - 1];
local nextAttribute <- machineBatchType[m][b];
local setupTime <- setupTimesMatrix[prevAttribute][nextAttribute];
// Setup and processing must fit in a single machine availability
constraint (
min(
(start(nextInterval) - setupTime)...end(nextInterval),
(t) => availabilities[m][t]
)
>= 1
);
}
// Total batch processing time
batchProcessingTime <-
sum[m in 0...nbMachines][b in 0...nbMaxBatch](
machineBatchUsed[m][b] * length(machineBatchInterval[m][b])
);
// Number of tardy jobs
tardyJobs <- sum[j in 0...nbJobs](end(jobInterval[j]) > jobDueDate[j]);
// Total setup costs
setupCosts <- sum[m in 0...nbMachines](machineSetupCosts[m]);
// Total setup times
setupTimes <- sum[m in 0...nbMachines](machineSetupTimes[m]);
// Minimize weighted processing time, tardy jobs, and setup costs
objective <-
weightBatchProcessingTime * batchProcessingTime
+ weightTardyJobs * tardyJobs
+ weightSetupCosts * setupCosts
+ weightSetupTimes * setupTimes;
minimize objective;
}
/* Parameterize the solver */
function param() {
if (hxTimeLimit == nil) hxTimeLimit = 15;
}
/* Write the solution in a file */
function output() {
if (solFileName == nil) return;
local solFile = io.openWrite(solFileName);
solFile.println("Objective: ", objective.value);
solFile.println("Machine Start End Jobs");
for [m in 0...nbMachines][b in 0...nbMaxBatch] {
if (!machineBatchUsed[m][b].value) continue;
solFile.print(
"Machine: ",
m + 1,
" | Start: ",
machineBatchInterval[m][b].value.start,
" | End: ",
machineBatchInterval[m][b].value.end,
" | Jobs: "
);
for [j in machineBatchContent[m][b].value] {
solFile.print(j + 1, " ");
}
solFile.println();
}
solFile.close();
}- Execution (Windows)
-
set PYTHONPATH=%HX_HOME%\bin\pythonpython oven_scheduling_problem.py instances\21-n25-k2-a2.dat
- Execution (Linux)
-
export PYTHONPATH=/opt/hexaly_15_0/bin/pythonpython oven_scheduling_problem.py instances/21-n25-k2-a2.dat
# Copyright (c) Hexaly. Permission is hereby granted to use, copy,
# and modify this code for applications developed with Hexaly.
import sys
import hexaly.optimizer
def read_integers(filename):
with open(filename, "r") as f:
return [int(x) for x in f.read().split()]
#
# Create a step array from a dense array
#
def create_step_array(model, dense_array, horizon):
indexes = []
values = []
value = dense_array[0]
for t in range(1, horizon):
if dense_array[t] != value:
indexes.append(t)
values.append(value)
value = dense_array[t]
indexes.append(horizon)
values.append(value)
return model.step_array(model.array(indexes), model.array(values))
#
# Read instance data from the input file
#
def main(input_file, output_file=None, time_limit=60):
values = iter(read_integers(input_file))
horizon = next(values)
nb_attributes = next(values)
# Attribute 0 is reserved for empty batches
empty_attribute = 0
# Input only provides setup values for real destination attributes;
# transitions to empty batches are set to zero
setup_costs_matrix = [
[0 for _ in range(nb_attributes + 1)] for _ in range(nb_attributes + 1)
]
for a1 in range(nb_attributes + 1):
for a2 in range(nb_attributes + 1):
setup_costs_matrix[a1][a2] = (
0 if a2 == empty_attribute else next(values)
)
setup_times_matrix = [
[0 for _ in range(nb_attributes + 1)] for _ in range(nb_attributes + 1)
]
for a1 in range(nb_attributes + 1):
for a2 in range(nb_attributes + 1):
setup_times_matrix[a1][a2] = (
0 if a2 == empty_attribute else next(values)
)
nb_machines = next(values)
machine_min_capacity = [next(values) for _ in range(nb_machines)]
machine_max_capacity = [next(values) for _ in range(nb_machines)]
machine_initial_attribute = [next(values) for _ in range(nb_machines)]
nb_availabilities = next(values)
availability_start = [
[next(values) for _ in range(nb_availabilities)]
for _ in range(nb_machines)
]
availability_end = [
[next(values) for _ in range(nb_availabilities)]
for _ in range(nb_machines)
]
nb_jobs = next(values)
machine_eligibility = [
[False for _ in range(nb_machines)] for _ in range(nb_jobs)
]
for j in range(nb_jobs):
nb_eligible = next(values)
for _ in range(nb_eligible):
machine_id = next(values)
# The machine IDs in the input start at 1
machine_eligibility[j][machine_id - 1] = True
job_release_date = [next(values) for _ in range(nb_jobs)]
job_due_date = [next(values) for _ in range(nb_jobs)]
job_min_processing_time = [next(values) for _ in range(nb_jobs)]
job_max_processing_time = [next(values) for _ in range(nb_jobs)]
job_size = [next(values) for _ in range(nb_jobs)]
job_attribute = [next(values) for _ in range(nb_jobs)]
upper_bound_integer_objective = next(values)
weight_batch_processing_time = next(values)
weight_tardy_jobs = next(values)
weight_setup_times = next(values)
weight_setup_costs = next(values)
#
# Preprocess instance data
#
# Create availability arrays from availability windows
availabilities_dense = [
[0 for _ in range(horizon)] for _ in range(nb_machines)
]
for m in range(nb_machines):
for a in range(nb_availabilities):
for t in range(availability_start[m][a], availability_end[m][a]):
availabilities_dense[m][t] = 1
# Worst case: one job per batch and per machine
nb_max_batch = nb_jobs
nb_total_batch = nb_machines * nb_max_batch
with hexaly.optimizer.HexalyOptimizer() as optimizer:
#
# Declare the optimization model
#
model = optimizer.model
setup_costs_array = model.array(setup_costs_matrix)
setup_times_array = model.array(setup_times_matrix)
job_size_array = model.array(job_size)
job_attribute_array = model.array(job_attribute)
job_release_date_array = model.array(job_release_date)
job_due_date_array = model.array(job_due_date)
job_min_processing_time_array = model.array(job_min_processing_time)
job_max_processing_time_array = model.array(job_max_processing_time)
machine_max_capacity_array = model.array(machine_max_capacity)
machine_initial_attribute_array = model.array(machine_initial_attribute)
# Convert availability arrays into step arrays to save space
availabilities = [
create_step_array(model, availabilities_dense[m], horizon)
for m in range(nb_machines)
]
# Set decisions: jobs assigned to each batch
batch_content = [model.set(nb_jobs) for _ in range(nb_total_batch)]
# Interval decisions: time range of each batch
batch_interval = [
model.interval(0, horizon) for _ in range(nb_total_batch)
]
# Each job must be assigned to exactly one batch
model.constraint(model.partition(batch_content))
# View batches by machine and batch position
machine_batch_content = [
[batch_content[m * nb_max_batch + b] for b in range(nb_max_batch)]
for m in range(nb_machines)
]
# View time ranges by machine and batch position
machine_batch_interval = [
[batch_interval[m * nb_max_batch + b] for b in range(nb_max_batch)]
for m in range(nb_machines)
]
# Total size of each batch
size_lambda = model.lambda_function(lambda j: job_size_array[j])
machine_batch_size = [
[
model.sum(machine_batch_content[m][b], size_lambda)
for b in range(nb_max_batch)
]
for m in range(nb_machines)
]
# Identify non-empty batches
machine_batch_used = [
[
model.count(machine_batch_content[m][b]) > 0
for b in range(nb_max_batch)
]
for m in range(nb_machines)
]
# Identify common attribute of each batch
attribute_lambda = model.lambda_function(
lambda j: job_attribute_array[j]
)
machine_batch_type = [
[
model.iif(
machine_batch_used[m][b],
model.min(machine_batch_content[m][b], attribute_lambda),
empty_attribute,
)
for b in range(nb_max_batch)
]
for m in range(nb_machines)
]
# Batch selected for each job
batch_content_array = model.array(batch_content)
job_index = [model.find(batch_content_array, j) for j in range(nb_jobs)]
# Jobs in the same batch share the same time range
batch_interval_array = model.array(batch_interval)
job_interval = [
batch_interval_array[job_index[j]] for j in range(nb_jobs)
]
for j in range(nb_jobs):
# Jobs cannot start before their release date
model.constraint(
model.start(job_interval[j]) >= job_release_date_array[j]
)
# Batch length must satisfy each assigned job
model.constraint(
model.length(job_interval[j])
>= job_min_processing_time_array[j]
)
model.constraint(
model.length(job_interval[j])
<= job_max_processing_time_array[j]
)
for j in range(nb_jobs):
for m in range(nb_machines):
if not machine_eligibility[j][m]:
for b in range(nb_max_batch):
# Jobs can only be assigned to eligible machines
model.constraint(
model.not_(
model.contains(machine_batch_content[m][b], j)
)
)
for b in range(nb_total_batch):
# Each batch must consist of jobs with the same type
model.constraint(
model.count(model.distinct(batch_content[b], attribute_lambda))
<= 1
)
for m in range(nb_machines):
for b in range(nb_max_batch):
# Batch size cannot exceed the machine capacity
model.constraint(
machine_batch_size[m][b] <= machine_max_capacity_array[m]
)
for m in range(nb_machines):
for b in range(1, nb_max_batch):
prev_attribute = machine_batch_type[m][b - 1]
next_attribute = machine_batch_type[m][b]
setup_time = setup_times_array[prev_attribute][next_attribute]
# Non-overlap between batches, with sequence-dependent setup times
model.constraint(
model.end(machine_batch_interval[m][b - 1]) + setup_time
<= model.start(machine_batch_interval[m][b])
)
# Empty batches must be last to keep setups between non-empty batches
model.constraint(
machine_batch_used[m][b - 1] >= machine_batch_used[m][b]
)
for m in range(nb_machines):
setup_time = setup_times_array[machine_initial_attribute_array[m]][
machine_batch_type[m][0]
]
# Account for the setup time before the first batch for each machine
model.constraint(
model.start(machine_batch_interval[m][0]) >= setup_time
)
# Setup costs between each batch
machine_setup_costs = [None for _ in range(nb_machines)]
for m in range(nb_machines):
machine_setup_costs[m] = model.sum(
[
setup_costs_array
[machine_batch_type[m][b - 1]]
[machine_batch_type[m][b]]
for b in range(1, nb_max_batch)
]
)
# Setup times between each batch
machine_setup_times = [None for _ in range(nb_machines)]
for m in range(nb_machines):
machine_setup_times[m] = model.sum(
[
setup_times_array
[machine_batch_type[m][b - 1]]
[machine_batch_type[m][b]]
for b in range(1, nb_max_batch)
]
)
for m in range(nb_machines):
availability = availabilities[m]
availability_lambda = model.lambda_function(
lambda t: availability[t]
)
for b in range(nb_max_batch):
next_interval = machine_batch_interval[m][b]
prev_attribute = model.iif(
b == 0,
empty_attribute,
machine_batch_type[m][b - 1],
)
next_attribute = machine_batch_type[m][b]
setup_time = setup_times_array[prev_attribute][next_attribute]
# Setup and processing must fit in a single machine availability
model.constraint(
model.min(
model.range(
model.start(next_interval) - setup_time,
model.end(next_interval),
),
availability_lambda,
)
>= 1
)
# Total batch processing time
batch_processing_time = model.sum(
[
machine_batch_used[m][b]
* model.length(machine_batch_interval[m][b])
for m in range(nb_machines)
for b in range(nb_max_batch)
]
)
# Number of tardy jobs
tardy_jobs = model.sum(
[
model.end(job_interval[j]) > job_due_date_array[j]
for j in range(nb_jobs)
]
)
# Total setup costs
setup_costs = model.sum(machine_setup_costs)
# Total setup times
setup_times = model.sum(machine_setup_times)
# Minimize weighted processing time, tardy jobs, and setup costs
objective = (
weight_batch_processing_time * batch_processing_time
+ weight_tardy_jobs * tardy_jobs
+ weight_setup_costs * setup_costs
+ weight_setup_times * setup_times
)
model.minimize(objective)
model.close()
#
# Parameterize the solver
#
optimizer.param.time_limit = time_limit
optimizer.solve()
write_solution(
output_file,
nb_machines,
nb_max_batch,
machine_batch_used,
machine_batch_interval,
machine_batch_content,
objective,
)
#
# Write the solution in a file
#
def write_solution(
output_file,
nb_machines,
nb_max_batch,
machine_batch_used,
machine_batch_interval,
machine_batch_content,
objective,
):
if output_file is None:
return
with open(output_file, "w") as sol_file:
sol_file.write("Objective: %s\n" % objective.value)
sol_file.write("Machine Start End Jobs\n")
for m in range(nb_machines):
for b in range(nb_max_batch):
if not machine_batch_used[m][b].value:
continue
sol_file.write(
"Machine: %d | Start: %d | End: %d | Jobs: "
% (
m + 1,
machine_batch_interval[m][b].value.start(),
machine_batch_interval[m][b].value.end(),
)
)
for j in machine_batch_content[m][b].value:
sol_file.write("%d " % (j + 1))
sol_file.write("\n")
#
# Read instance data
#
if __name__ == "__main__":
usage = (
"Usage: python oven_scheduling_problem.py input_file [output_file] [time_limit]"
)
if len(sys.argv) < 2:
print(usage, file=sys.stderr)
sys.exit(1)
input_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 15
main(input_file, output_file, time_limit)
- Compilation / Execution (Windows)
-
cl /EHsc oven_scheduling_problem.cpp -I%HX_HOME%\include /link %HX_HOME%\bin\hexaly150.liboven_scheduling_problem instances\21-n25-k2-a2.dat
- Compilation / Execution (Linux)
-
g++ oven_scheduling_problem.cpp -I/opt/hexaly_15_0/include -lhexaly150 -lpthread -o oven_scheduling_problem./oven_scheduling_problem instances/21-n25-k2-a2.dat
// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
#include "optimizer/hexalyoptimizer.h"
#include <cstdlib>
#include <fstream>
#include <iostream>
#include <numeric>
#include <sstream>
#include <stdexcept>
#include <string>
#include <vector>
using namespace hexaly;
using namespace std;
class OvenScheduling {
private:
HexalyOptimizer optimizer;
int horizon;
int nbAttributes;
int emptyAttribute;
int nbMachines;
int nbAvailabilities;
int nbJobs;
int nbMaxBatch;
int nbTotalBatch;
vector<vector<hxint>> setupCostsMatrixData;
vector<vector<hxint>> setupTimesMatrixData;
vector<hxint> machineMinCapacity;
vector<hxint> machineMaxCapacity;
vector<hxint> machineInitialAttribute;
vector<vector<hxint>> availabilityStart;
vector<vector<hxint>> availabilityEnd;
vector<vector<bool>> machineEligibility;
vector<hxint> jobReleaseDate;
vector<hxint> jobDueDate;
vector<hxint> jobMinProcessingTime;
vector<hxint> jobMaxProcessingTime;
vector<hxint> jobSize;
vector<hxint> jobAttribute;
hxint upperBoundIntegerObjective;
hxint weightBatchProcessingTime;
hxint weightTardyJobs;
hxint weightSetupTimes;
hxint weightSetupCosts;
HxExpression setupCostsMatrix;
HxExpression setupTimesMatrix;
HxExpression jobSizeArray;
HxExpression jobAttributeArray;
HxExpression batchContentArray;
HxExpression batchIntervalArray;
vector<vector<hxint>> availabilitiesDenseData;
vector<HxExpression> availabilities;
vector<HxExpression> batchContent;
vector<HxExpression> batchInterval;
vector<vector<HxExpression>> machineBatchContent;
vector<vector<HxExpression>> machineBatchInterval;
vector<vector<HxExpression>> machineBatchSize;
vector<vector<HxExpression>> machineBatchUsed;
vector<vector<HxExpression>> machineBatchType;
vector<HxExpression> jobIndex;
vector<HxExpression> jobInterval;
vector<HxExpression> machineSetupCosts;
vector<HxExpression> machineSetupTimes;
HxExpression batchProcessingTime;
HxExpression tardyJobs;
HxExpression setupCosts;
HxExpression setupTimes;
HxExpression objective;
static void throwIf(bool condition, const string& message) {
if (condition)
throw runtime_error(message);
}
HxExpression createArray2D(HxModel& model, const vector<vector<hxint>>& data) {
vector<HxExpression> rows(data.size());
for (int i = 0; i < (int)data.size(); ++i) {
rows[i] = model.array(data[i].begin(), data[i].end());
}
return model.array(rows.begin(), rows.end());
}
/* Create a step array from a dense array */
HxExpression createStepArray(HxModel& model, const vector<hxint>& denseArray) {
vector<hxint> indexes;
vector<hxint> values;
hxint value = denseArray[0];
for (int t = 1; t < horizon; ++t) {
if (denseArray[t] != value) {
indexes.push_back(t);
values.push_back(value);
value = denseArray[t];
}
}
indexes.push_back(horizon);
values.push_back(value);
HxExpression indexArray = model.array(indexes.begin(), indexes.end());
HxExpression valueArray = model.array(values.begin(), values.end());
return model.stepArray(indexArray, valueArray);
}
public:
/* Read instance data from the input file */
void readInstance(const string& fileName) {
ifstream inFile;
inFile.exceptions(ifstream::failbit | ifstream::badbit);
inFile.open(fileName.c_str());
inFile >> horizon;
inFile >> nbAttributes;
// Attribute 0 is reserved for empty batches
emptyAttribute = 0;
// Input only provides setup values for real destination attributes;
// transitions to empty batches are set to zero
setupCostsMatrixData.assign(
nbAttributes + 1,
vector<hxint>(nbAttributes + 1, 0));
for (int a1 = 0; a1 < nbAttributes + 1; ++a1) {
for (int a2 = 0; a2 < nbAttributes + 1; ++a2) {
if (a2 == emptyAttribute) {
setupCostsMatrixData[a1][a2] = 0;
} else {
inFile >> setupCostsMatrixData[a1][a2];
}
}
}
setupTimesMatrixData.assign(
nbAttributes + 1,
vector<hxint>(nbAttributes + 1, 0));
for (int a1 = 0; a1 < nbAttributes + 1; ++a1) {
for (int a2 = 0; a2 < nbAttributes + 1; ++a2) {
if (a2 == emptyAttribute) {
setupTimesMatrixData[a1][a2] = 0;
} else {
inFile >> setupTimesMatrixData[a1][a2];
}
}
}
inFile >> nbMachines;
machineMinCapacity.resize(nbMachines);
for (int m = 0; m < nbMachines; ++m)
inFile >> machineMinCapacity[m];
machineMaxCapacity.resize(nbMachines);
for (int m = 0; m < nbMachines; ++m)
inFile >> machineMaxCapacity[m];
machineInitialAttribute.resize(nbMachines);
for (int m = 0; m < nbMachines; ++m)
inFile >> machineInitialAttribute[m];
inFile >> nbAvailabilities;
availabilityStart.assign(nbMachines, vector<hxint>(nbAvailabilities));
for (int m = 0; m < nbMachines; ++m) {
for (int a = 0; a < nbAvailabilities; ++a) {
inFile >> availabilityStart[m][a];
}
}
availabilityEnd.assign(nbMachines, vector<hxint>(nbAvailabilities));
for (int m = 0; m < nbMachines; ++m) {
for (int a = 0; a < nbAvailabilities; ++a) {
inFile >> availabilityEnd[m][a];
}
}
inFile >> nbJobs;
machineEligibility.assign(nbJobs, vector<bool>(nbMachines, false));
for (int j = 0; j < nbJobs; ++j) {
int nbEligible;
inFile >> nbEligible;
for (int e = 0; e < nbEligible; ++e) {
int machineId;
inFile >> machineId;
// The machine IDs in the input start at 1
machineEligibility[j][machineId - 1] = true;
}
}
jobReleaseDate.resize(nbJobs);
for (int j = 0; j < nbJobs; ++j)
inFile >> jobReleaseDate[j];
jobDueDate.resize(nbJobs);
for (int j = 0; j < nbJobs; ++j)
inFile >> jobDueDate[j];
jobMinProcessingTime.resize(nbJobs);
for (int j = 0; j < nbJobs; ++j)
inFile >> jobMinProcessingTime[j];
jobMaxProcessingTime.resize(nbJobs);
for (int j = 0; j < nbJobs; ++j)
inFile >> jobMaxProcessingTime[j];
jobSize.resize(nbJobs);
for (int j = 0; j < nbJobs; ++j)
inFile >> jobSize[j];
jobAttribute.resize(nbJobs);
for (int j = 0; j < nbJobs; ++j)
inFile >> jobAttribute[j];
inFile >> upperBoundIntegerObjective;
inFile >> weightBatchProcessingTime;
inFile >> weightTardyJobs;
inFile >> weightSetupTimes;
inFile >> weightSetupCosts;
inFile.close();
}
/* Preprocess instance data */
void preprocessData() {
// Worst case: one job per batch and per machine
nbMaxBatch = nbJobs;
nbTotalBatch = nbMachines * nbMaxBatch;
}
/* Declare the optimization model */
void solve(int timeLimit) {
HxModel model = optimizer.getModel();
setupCostsMatrix = createArray2D(model, setupCostsMatrixData);
setupTimesMatrix = createArray2D(model, setupTimesMatrixData);
jobSizeArray = model.array(jobSize.begin(), jobSize.end());
jobAttributeArray = model.array(jobAttribute.begin(), jobAttribute.end());
// Create availability arrays from availability windows
availabilities.resize(nbMachines);
availabilitiesDenseData.assign(nbMachines, vector<hxint>(horizon, 0));
for (int m = 0; m < nbMachines; ++m) {
for (int a = 0; a < nbAvailabilities; ++a) {
for (int t = (int)availabilityStart[m][a];
t < (int)availabilityEnd[m][a];
++t) {
availabilitiesDenseData[m][t] = 1;
}
}
// Convert availability arrays into step arrays to save space
availabilities[m] = createStepArray(model, availabilitiesDenseData[m]);
}
batchContent.resize(nbTotalBatch);
batchInterval.resize(nbTotalBatch);
// Set decisions: jobs assigned to each batch
for (int b = 0; b < nbTotalBatch; ++b) {
batchContent[b] = model.setVar(nbJobs);
}
// Interval decisions: time range of each batch
for (int b = 0; b < nbTotalBatch; ++b) {
batchInterval[b] = model.intervalVar(0, horizon);
}
batchContentArray = model.array(batchContent.begin(), batchContent.end());
batchIntervalArray = model.array(batchInterval.begin(), batchInterval.end());
// Each job must be assigned to exactly one batch
model.constraint(model.partition(batchContent.begin(), batchContent.end()));
machineBatchContent.assign(nbMachines, vector<HxExpression>(nbMaxBatch));
machineBatchInterval.assign(nbMachines, vector<HxExpression>(nbMaxBatch));
machineBatchSize.assign(nbMachines, vector<HxExpression>(nbMaxBatch));
machineBatchUsed.assign(nbMachines, vector<HxExpression>(nbMaxBatch));
machineBatchType.assign(nbMachines, vector<HxExpression>(nbMaxBatch));
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
int index = m * nbMaxBatch + b;
// View batches by machine and batch position
machineBatchContent[m][b] = batchContent[index];
// View time ranges by machine and batch position
machineBatchInterval[m][b] = batchInterval[index];
}
}
HxExpression sizeLambda = model.createLambdaFunction(
[&](HxExpression j) { return jobSizeArray[j]; });
HxExpression attributeLambda = model.createLambdaFunction(
[&](HxExpression j) { return jobAttributeArray[j]; });
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
// Total size of each batch
machineBatchSize[m][b]
= model.sum(machineBatchContent[m][b], sizeLambda);
// Identify non-empty batches
machineBatchUsed[m][b] = model.count(machineBatchContent[m][b]) > 0;
// Identify common attribute of each batch
machineBatchType[m][b] = model.iif(
machineBatchUsed[m][b],
model.min(machineBatchContent[m][b], attributeLambda),
emptyAttribute);
}
}
jobIndex.resize(nbJobs);
jobInterval.resize(nbJobs);
for (int j = 0; j < nbJobs; ++j) {
// Batch selected for each job
jobIndex[j] = model.find(batchContentArray, j);
// Jobs in the same batch share the same time range
jobInterval[j] = batchIntervalArray[jobIndex[j]];
// Jobs cannot start before their release date
model.constraint(model.start(jobInterval[j]) >= jobReleaseDate[j]);
// Batch length must satisfy each assigned job
model.constraint(
model.length(jobInterval[j]) >= jobMinProcessingTime[j]);
model.constraint(
model.length(jobInterval[j]) <= jobMaxProcessingTime[j]);
}
for (int j = 0; j < nbJobs; ++j) {
for (int m = 0; m < nbMachines; ++m) {
if (!machineEligibility[j][m]) {
for (int b = 0; b < nbMaxBatch; ++b) {
// Jobs can only be assigned to eligible machines
model.constraint(
model.contains(machineBatchContent[m][b], j) == 0);
}
}
}
}
for (int b = 0; b < nbTotalBatch; ++b) {
// Each batch must consist of jobs with the same type
model.constraint(
model.count(model.distinct(batchContent[b], attributeLambda))
<= 1);
}
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
// Batch size cannot exceed the machine capacity
model.constraint(machineBatchSize[m][b] <= machineMaxCapacity[m]);
}
}
for (int m = 0; m < nbMachines; ++m) {
for (int b = 1; b < nbMaxBatch; ++b) {
HxExpression prevAttribute = machineBatchType[m][b - 1];
HxExpression nextAttribute = machineBatchType[m][b];
HxExpression setupTime
= model.at(setupTimesMatrix, prevAttribute, nextAttribute);
// Non-overlap between batches, with sequence-dependent setup times
model.constraint(
model.end(machineBatchInterval[m][b - 1]) + setupTime
<= model.start(machineBatchInterval[m][b]));
// Empty batches must be last to keep setups between non-empty batches
model.constraint(
machineBatchUsed[m][b - 1] >= machineBatchUsed[m][b]);
}
}
for (int m = 0; m < nbMachines; ++m) {
HxExpression setupTime = model.at(
setupTimesMatrix,
machineInitialAttribute[m],
machineBatchType[m][0]);
// Account for the setup time before the first batch for each machine
model.constraint(model.start(machineBatchInterval[m][0]) >= setupTime);
}
// Setup costs between each batch
machineSetupCosts.resize(nbMachines);
for (int m = 0; m < nbMachines; ++m) {
vector<HxExpression> setupTerms;
setupTerms.reserve(nbMaxBatch);
for (int b = 1; b < nbMaxBatch; ++b) {
HxExpression prevAttribute = machineBatchType[m][b - 1];
HxExpression nextAttribute = machineBatchType[m][b];
setupTerms.push_back(
model.at(setupCostsMatrix, prevAttribute, nextAttribute));
}
machineSetupCosts[m] = model.sum(setupTerms.begin(), setupTerms.end());
}
// Setup times between each batch
machineSetupTimes.resize(nbMachines);
for (int m = 0; m < nbMachines; ++m) {
vector<HxExpression> setupTerms;
setupTerms.reserve(nbMaxBatch);
for (int b = 1; b < nbMaxBatch; ++b) {
HxExpression prevAttribute = machineBatchType[m][b - 1];
HxExpression nextAttribute = machineBatchType[m][b];
setupTerms.push_back(
model.at(setupTimesMatrix, prevAttribute, nextAttribute));
}
machineSetupTimes[m] = model.sum(setupTerms.begin(), setupTerms.end());
}
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
HxExpression next = machineBatchInterval[m][b];
HxExpression prevAttribute
= (b == 0) ? model.createConstant((hxint)emptyAttribute)
: machineBatchType[m][b - 1];
HxExpression nextAttribute = machineBatchType[m][b];
HxExpression setupTime
= model.at(setupTimesMatrix, prevAttribute, nextAttribute);
HxExpression availabilityLambda
= model.createLambdaFunction([&, m](HxExpression t) {
return model.at(availabilities[m], t);
});
// Setup and processing must fit in a single machine availability
model.constraint(
model.min(
model.range(
model.start(next) - setupTime,
model.end(next)),
availabilityLambda)
>= 1);
}
}
vector<HxExpression> processingTerms;
processingTerms.reserve(nbMachines * nbMaxBatch);
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
processingTerms.push_back(
machineBatchUsed[m][b]
* model.length(machineBatchInterval[m][b]));
}
}
// Total batch processing time
batchProcessingTime
= model.sum(processingTerms.begin(), processingTerms.end());
vector<HxExpression> tardyTerms;
tardyTerms.reserve(nbJobs);
for (int j = 0; j < nbJobs; ++j) {
tardyTerms.push_back(model.end(jobInterval[j]) > jobDueDate[j]);
}
// Number of tardy jobs
tardyJobs = model.sum(tardyTerms.begin(), tardyTerms.end());
// Total setup costs
setupCosts = model.sum(machineSetupCosts.begin(), machineSetupCosts.end());
// Total setup times
setupTimes = model.sum(machineSetupTimes.begin(), machineSetupTimes.end());
// Minimize weighted processing time, tardy jobs, and setup costs
objective = weightBatchProcessingTime * batchProcessingTime
+ weightTardyJobs * tardyJobs
+ weightSetupCosts * setupCosts
+ weightSetupTimes * setupTimes;
model.minimize(objective);
model.close();
/* Parameterize the solver */
optimizer.getParam().setTimeLimit(timeLimit);
optimizer.solve();
}
/* Write the solution in a file */
void writeSolution(const string& fileName) {
ofstream outputFile;
outputFile.exceptions(ofstream::failbit | ofstream::badbit);
outputFile.open(fileName.c_str());
outputFile << "Objective: " << objective.getValue() << endl;
outputFile << "Machine Start End Jobs" << endl;
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
if (!machineBatchUsed[m][b].getValue())
continue;
HxInterval intervalValue
= machineBatchInterval[m][b].getIntervalValue();
outputFile << "Machine: " << (m + 1)
<< " | Start: " << intervalValue.getStart()
<< " | End: " << intervalValue.getEnd() << " | Jobs: ";
HxCollection jobs = machineBatchContent[m][b].getCollectionValue();
for (int i = 0; i < jobs.count(); ++i) {
outputFile << (jobs[i] + 1) << " ";
}
outputFile << endl;
}
}
outputFile.close();
}
};
/* Read instance data */
int main(int argc, char** argv) {
const char* usage = "Usage: oven_scheduling_problem inputFile [outputFile] [timeLimit]";
if (argc < 2) {
cerr << usage << endl;
return 1;
}
const char* instanceFile = argv[1];
const char* outputFile = argc > 2 ? argv[2] : NULL;
const char* strTimeLimit = argc > 3 ? argv[3] : "15";
int timeLimit = atoi(strTimeLimit);
try {
OvenScheduling model;
model.readInstance(instanceFile);
model.preprocessData();
model.solve(timeLimit);
if (outputFile != NULL) {
model.writeSolution(outputFile);
}
return 0;
} catch (const exception& e) {
cerr << "An error occurred: " << e.what() << endl;
return 1;
}
}
- Compilation / Execution (Windows)
-
copy %HX_HOME%\bin\Hexaly.NET.dll .csc OvenSchedulingProblem.cs /reference:Hexaly.NET.dllOvenSchedulingProblem instances\21-n25-k2-a2.dat
// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
using System;
using System.Collections.Generic;
using System.Globalization;
using System.IO;
using System.Linq;
using Hexaly.Optimizer;
public class OvenSchedulingProblem
{
private readonly HexalyOptimizer optimizer;
private int horizon;
private int nbAttributes;
// Attribute 0 is reserved for empty batches
private const int emptyAttribute = 0;
private int nbMachines;
private int nbAvailabilities;
private int nbJobs;
private int nbMaxBatch;
private int nbTotalBatch;
private long[,] setupCostsMatrix;
private long[,] setupTimesMatrix;
private long[] machineMinCapacity;
private long[] machineMaxCapacity;
private int[] machineInitialAttribute;
private int[,] availabilityStart;
private int[,] availabilityEnd;
private bool[,] machineEligibility;
private long[] jobReleaseDate;
private long[] jobDueDate;
private long[] jobMinProcessingTime;
private long[] jobMaxProcessingTime;
private long[] jobSize;
private int[] jobAttribute;
private long upperBoundIntegerObjective;
private long weightBatchProcessingTime;
private long weightTardyJobs;
private long weightSetupTimes;
private long weightSetupCosts;
private long[][] availabilityDense;
private HxExpression[] batchContent;
private HxExpression[] batchInterval;
private HxExpression[,] machineBatchContent;
private HxExpression[,] machineBatchInterval;
private HxExpression[,] machineBatchSize;
private HxExpression[,] machineBatchUsed;
private HxExpression[,] machineBatchType;
private HxExpression[] jobIndex;
private HxExpression[] jobInterval;
private HxExpression batchProcessingTime;
private HxExpression tardyJobs;
private HxExpression setupCosts;
private HxExpression setupTimes;
private HxExpression objective;
public OvenSchedulingProblem(HexalyOptimizer optimizer)
{
this.optimizer = optimizer;
}
private sealed class IntReader : IDisposable
{
private readonly string[] tokens;
private int index;
public IntReader(string fileName)
{
tokens = File.ReadAllText(fileName)
.Split((char[])null, StringSplitOptions.RemoveEmptyEntries);
index = 0;
}
public int NextInt()
{
return int.Parse(tokens[index++], CultureInfo.InvariantCulture);
}
public long NextLong()
{
return long.Parse(tokens[index++], CultureInfo.InvariantCulture);
}
public void Dispose()
{
}
}
/* Read instance data from the input file */
private void ReadInstance(string fileName)
{
using (IntReader input = new IntReader(fileName))
{
horizon = input.NextInt();
nbAttributes = input.NextInt();
// Input only provides setup values for real destination attributes;
// transitions to empty batches are set to zero
setupCostsMatrix = new long[nbAttributes + 1, nbAttributes + 1];
for (int a1 = 0; a1 <= nbAttributes; ++a1)
{
for (int a2 = 0; a2 <= nbAttributes; ++a2)
{
setupCostsMatrix[a1, a2] =
a2 == emptyAttribute ? 0 : input.NextLong();
}
}
setupTimesMatrix = new long[nbAttributes + 1, nbAttributes + 1];
for (int a1 = 0; a1 <= nbAttributes; ++a1)
{
for (int a2 = 0; a2 <= nbAttributes; ++a2)
{
setupTimesMatrix[a1, a2] =
a2 == emptyAttribute ? 0 : input.NextLong();
}
}
nbMachines = input.NextInt();
machineMinCapacity = new long[nbMachines];
machineMaxCapacity = new long[nbMachines];
machineInitialAttribute = new int[nbMachines];
for (int m = 0; m < nbMachines; ++m)
machineMinCapacity[m] = input.NextLong();
for (int m = 0; m < nbMachines; ++m)
machineMaxCapacity[m] = input.NextLong();
for (int m = 0; m < nbMachines; ++m)
machineInitialAttribute[m] = input.NextInt();
nbAvailabilities = input.NextInt();
availabilityStart = new int[nbMachines, nbAvailabilities];
availabilityEnd = new int[nbMachines, nbAvailabilities];
for (int m = 0; m < nbMachines; ++m)
{
for (int a = 0; a < nbAvailabilities; ++a)
{
availabilityStart[m, a] = input.NextInt();
}
}
for (int m = 0; m < nbMachines; ++m)
{
for (int a = 0; a < nbAvailabilities; ++a)
{
availabilityEnd[m, a] = input.NextInt();
}
}
nbJobs = input.NextInt();
machineEligibility = new bool[nbJobs, nbMachines];
for (int j = 0; j < nbJobs; ++j)
{
int nbEligible = input.NextInt();
for (int e = 0; e < nbEligible; ++e)
{
int machineId = input.NextInt();
// The machine IDs in the input start at 1
machineEligibility[j, machineId - 1] = true;
}
}
jobReleaseDate = new long[nbJobs];
jobDueDate = new long[nbJobs];
jobMinProcessingTime = new long[nbJobs];
jobMaxProcessingTime = new long[nbJobs];
jobSize = new long[nbJobs];
jobAttribute = new int[nbJobs];
for (int j = 0; j < nbJobs; ++j)
jobReleaseDate[j] = input.NextLong();
for (int j = 0; j < nbJobs; ++j)
jobDueDate[j] = input.NextLong();
for (int j = 0; j < nbJobs; ++j)
jobMinProcessingTime[j] = input.NextLong();
for (int j = 0; j < nbJobs; ++j)
jobMaxProcessingTime[j] = input.NextLong();
for (int j = 0; j < nbJobs; ++j)
jobSize[j] = input.NextLong();
for (int j = 0; j < nbJobs; ++j)
jobAttribute[j] = input.NextInt();
upperBoundIntegerObjective = input.NextLong();
weightBatchProcessingTime = input.NextLong();
weightTardyJobs = input.NextLong();
weightSetupTimes = input.NextLong();
weightSetupCosts = input.NextLong();
}
}
/* Preprocess instance data */
private void PreprocessData()
{
// Create availability arrays from availability windows
availabilityDense = new long[nbMachines][];
for (int m = 0; m < nbMachines; ++m)
{
availabilityDense[m] = new long[horizon];
for (int a = 0; a < nbAvailabilities; ++a)
{
int start = availabilityStart[m, a];
int end = availabilityEnd[m, a];
for (int t = start; t < end; ++t)
{
if (0 <= t && t < horizon)
{
availabilityDense[m][t] = 1;
}
}
}
}
// Worst case: one job per batch and per machine
nbMaxBatch = nbJobs;
nbTotalBatch = nbMachines * nbMaxBatch;
}
/* Create a step array from a dense array */
private HxExpression CreateStepArray(HxModel model, long[] denseArray)
{
List<long> indexes = new List<long>();
List<long> values = new List<long>();
long value = denseArray[0];
for (int t = 1; t < horizon; ++t)
{
if (denseArray[t] != value)
{
indexes.Add(t);
values.Add(value);
value = denseArray[t];
}
}
indexes.Add(horizon);
values.Add(value);
return model.StepArray(
model.Array(indexes.ToArray()), model.Array(values.ToArray()));
}
private HxExpression CreateMatrix(HxModel model, long[,] matrix)
{
int rows = matrix.GetLength(0);
int cols = matrix.GetLength(1);
HxExpression[] rowExpressions = new HxExpression[rows];
for (int i = 0; i < rows; ++i)
{
long[] row = new long[cols];
for (int j = 0; j < cols; ++j)
{
row[j] = matrix[i, j];
}
rowExpressions[i] = model.Array(row);
}
return model.Array(rowExpressions);
}
private HxExpression CreateArray(HxModel model, int[] values)
{
long[] longValues = values.Select(v => (long)v).ToArray();
return model.Array(longValues);
}
/* Declare the optimization model */
private void Solve(int timeLimit)
{
HxModel model = optimizer.GetModel();
HxExpression setupCostsArray = CreateMatrix(model, setupCostsMatrix);
HxExpression setupTimesArray = CreateMatrix(model, setupTimesMatrix);
HxExpression jobSizeArray = model.Array(jobSize);
HxExpression jobAttributeArray = CreateArray(model, jobAttribute);
HxExpression jobReleaseDateArray = model.Array(jobReleaseDate);
HxExpression jobDueDateArray = model.Array(jobDueDate);
HxExpression jobMinProcessingTimeArray = model.Array(jobMinProcessingTime);
HxExpression jobMaxProcessingTimeArray = model.Array(jobMaxProcessingTime);
HxExpression machineMaxCapacityArray = model.Array(machineMaxCapacity);
HxExpression machineInitialAttributeArray
= CreateArray(model, machineInitialAttribute);
HxExpression[] availabilities = new HxExpression[nbMachines];
// Convert availability arrays into step arrays to save space
for (int m = 0; m < nbMachines; ++m)
{
availabilities[m] = CreateStepArray(model, availabilityDense[m]);
}
batchContent = new HxExpression[nbTotalBatch];
batchInterval = new HxExpression[nbTotalBatch];
// Set decisions: jobs assigned to each batch
for (int b = 0; b < nbTotalBatch; ++b)
{
batchContent[b] = model.Set(nbJobs);
}
// Interval decisions: time range of each batch
for (int b = 0; b < nbTotalBatch; ++b)
{
batchInterval[b] = model.Interval(0, horizon);
}
// Each job must be assigned to exactly one batch
model.Constraint(model.Partition(batchContent));
HxExpression batchContentArray = model.Array(batchContent);
HxExpression batchIntervalArray = model.Array(batchInterval);
machineBatchContent = new HxExpression[nbMachines, nbMaxBatch];
machineBatchInterval = new HxExpression[nbMachines, nbMaxBatch];
for (int m = 0; m < nbMachines; ++m)
{
for (int b = 0; b < nbMaxBatch; ++b)
{
int index = m * nbMaxBatch + b;
// View batches by machine and batch position
machineBatchContent[m, b] = batchContent[index];
// View time ranges by machine and batch position
machineBatchInterval[m, b] = batchInterval[index];
}
}
HxExpression sizeLambda = model.LambdaFunction(
j => model.At(jobSizeArray, j));
HxExpression attributeLambda = model.LambdaFunction(
j => model.At(jobAttributeArray, j));
machineBatchSize = new HxExpression[nbMachines, nbMaxBatch];
machineBatchUsed = new HxExpression[nbMachines, nbMaxBatch];
machineBatchType = new HxExpression[nbMachines, nbMaxBatch];
for (int m = 0; m < nbMachines; ++m)
{
for (int b = 0; b < nbMaxBatch; ++b)
{
HxExpression content = machineBatchContent[m, b];
// Total size of each batch
machineBatchSize[m, b] = model.Sum(content, sizeLambda);
// Identify non-empty batches
machineBatchUsed[m, b] = model.Gt(model.Count(content), 0);
// Identify common attribute of each batch
machineBatchType[m, b] = model.If(
machineBatchUsed[m, b],
model.Min(content, attributeLambda),
emptyAttribute
);
}
}
jobIndex = new HxExpression[nbJobs];
jobInterval = new HxExpression[nbJobs];
for (int j = 0; j < nbJobs; ++j)
{
// Batch selected for each job
jobIndex[j] = model.Find(batchContentArray, j);
// Jobs in the same batch share the same time range
jobInterval[j] = model.At(batchIntervalArray, jobIndex[j]);
}
for (int j = 0; j < nbJobs; ++j)
{
HxExpression interval = jobInterval[j];
// Jobs cannot start before their release date
model.Constraint(model.Geq(
model.Start(interval), model.At(jobReleaseDateArray, j)));
// Batch length must satisfy each assigned job
model.Constraint(model.Geq(
model.Length(interval), model.At(jobMinProcessingTimeArray, j)));
model.Constraint(model.Leq(
model.Length(interval), model.At(jobMaxProcessingTimeArray, j)));
}
// Jobs can only be assigned to eligible machines
for (int j = 0; j < nbJobs; ++j)
{
for (int m = 0; m < nbMachines; ++m)
{
if (!machineEligibility[j, m])
{
for (int b = 0; b < nbMaxBatch; ++b)
{
model.Constraint(model.Not(
model.Contains(machineBatchContent[m, b], j)));
}
}
}
}
// Each batch must consist of jobs with the same type
for (int b = 0; b < nbTotalBatch; ++b)
{
model.Constraint(model.Leq(model.Count(
model.Distinct(batchContent[b], attributeLambda)), 1));
}
// Batch size cannot exceed the machine capacity
for (int m = 0; m < nbMachines; ++m)
{
for (int b = 0; b < nbMaxBatch; ++b)
{
model.Constraint(model.Leq(machineBatchSize[m, b],
model.At(machineMaxCapacityArray, m)));
}
}
// Non-overlap between batches, with sequence-dependent setup times
for (int m = 0; m < nbMachines; ++m)
{
for (int b = 1; b < nbMaxBatch; ++b)
{
HxExpression prevAttribute = machineBatchType[m, b - 1];
HxExpression nextAttribute = machineBatchType[m, b];
HxExpression setupTime = model.At(setupTimesArray,
prevAttribute, nextAttribute);
model.Constraint(model.Leq(
model.Sum(model.End(machineBatchInterval[m, b - 1]), setupTime),
model.Start(machineBatchInterval[m, b])));
// Empty batches must be last to keep setups between non-empty batches
model.Constraint(model.Geq(
machineBatchUsed[m, b - 1], machineBatchUsed[m, b]));
}
}
// Account for the setup time before the first batch for each machine
for (int m = 0; m < nbMachines; ++m)
{
HxExpression setupTime = model.At(
setupTimesArray,
model.At(machineInitialAttributeArray, m),
machineBatchType[m, 0]
);
model.Constraint(model.Geq(
model.Start(machineBatchInterval[m, 0]), setupTime));
}
// Setup costs between each batch
HxExpression[] machineSetupCosts = new HxExpression[nbMachines];
for (int m = 0; m < nbMachines; ++m)
{
HxExpression sum = model.Sum();
for (int b = 1; b < nbMaxBatch; ++b)
{
HxExpression prevAttribute = machineBatchType[m, b - 1];
HxExpression nextAttribute = machineBatchType[m, b];
sum.AddOperand(model.At(setupCostsArray,
prevAttribute, nextAttribute));
}
machineSetupCosts[m] = sum;
}
// Setup times between each batch
HxExpression[] machineSetupTimes = new HxExpression[nbMachines];
for (int m = 0; m < nbMachines; ++m)
{
HxExpression sum = model.Sum();
for (int b = 1; b < nbMaxBatch; ++b)
{
HxExpression prevAttribute = machineBatchType[m, b - 1];
HxExpression nextAttribute = machineBatchType[m, b];
sum.AddOperand(model.At(setupTimesArray,
prevAttribute, nextAttribute));
}
machineSetupTimes[m] = sum;
}
for (int m = 0; m < nbMachines; ++m)
{
int machine = m;
HxExpression availabilityLambda =
model.LambdaFunction(t => model.At(availabilities[machine], t));
for (int b = 0; b < nbMaxBatch; ++b)
{
HxExpression next = machineBatchInterval[m, b];
HxExpression prevAttribute = b == 0
? model.CreateConstant(emptyAttribute)
: machineBatchType[m, b - 1];
HxExpression nextAttribute = machineBatchType[m, b];
HxExpression setupTime = model.At(setupTimesArray,
prevAttribute, nextAttribute);
// Setup and processing must fit in a single machine availability
model.Constraint(
model.Geq(
model.Min(model.Range(
model.Sub(model.Start(next), setupTime),
model.End(next)),
availabilityLambda),
1)
);
}
}
// Total batch processing time
HxExpression processingSum = model.Sum();
for (int m = 0; m < nbMachines; ++m)
{
for (int b = 0; b < nbMaxBatch; ++b)
{
processingSum.AddOperand(model.Prod(
machineBatchUsed[m, b],
model.Length(machineBatchInterval[m, b]))
);
}
}
batchProcessingTime = processingSum;
// Number of tardy jobs
HxExpression tardySum = model.Sum();
for (int j = 0; j < nbJobs; ++j)
{
tardySum.AddOperand(model.Gt(
model.End(jobInterval[j]), model.At(jobDueDateArray, j)));
}
tardyJobs = tardySum;
// Total setup costs
setupCosts = model.Sum(machineSetupCosts);
// Total setup times
setupTimes = model.Sum(machineSetupTimes);
// Minimize weighted processing time, tardy jobs, and setup costs
objective = model.Sum(
model.Prod(weightBatchProcessingTime, batchProcessingTime),
model.Prod(weightTardyJobs, tardyJobs),
model.Prod(weightSetupCosts, setupCosts),
model.Prod(weightSetupTimes, setupTimes)
);
model.Minimize(objective);
model.Close();
/* Parameterize the solver */
optimizer.GetParam().SetTimeLimit(timeLimit);
optimizer.Solve();
}
private List<int> JobsInBatch(int m, int b)
{
List<int> jobs = new List<int>();
HxCollection collection = machineBatchContent[m, b].GetCollectionValue();
foreach (long value in collection)
{
jobs.Add((int)value);
}
return jobs;
}
/* Write the solution in a file */
private void WriteSolution(string fileName)
{
if (fileName == null) return;
using (StreamWriter output = new StreamWriter(fileName))
{
output.WriteLine("Objective: " + objective.GetIntValue());
output.WriteLine("Machine Start End Jobs");
for (int m = 0; m < nbMachines; ++m)
{
for (int b = 0; b < nbMaxBatch; ++b)
{
if (machineBatchUsed[m, b].GetIntValue() == 0) continue;
HxInterval interval = machineBatchInterval[m, b].GetIntervalValue();
List<int> jobs = JobsInBatch(m, b);
output.Write(
"Machine: " + (m + 1)
+ " | Start: " + interval.Start()
+ " | End: " + interval.End()
+ " | Jobs: "
);
foreach (int j in jobs)
{
output.Write((j + 1) + " ");
}
output.WriteLine();
}
}
}
}
/* Read instance data */
public static void Main(string[] args)
{
string usage = "Usage: OvenSchedulingProblem inputFile [outputFile] [timeLimit]";
if (args.Length < 1)
{
Console.Error.WriteLine(usage);
Environment.Exit(1);
}
string inputFile = args[0];
string outputFile = args.Length > 1 ? args[1] : null;
string strTimeLimit = args.Length > 2 ? args[2] : "15";
int timeLimit = int.Parse(strTimeLimit);
try
{
using (HexalyOptimizer optimizer = new HexalyOptimizer())
{
OvenSchedulingProblem model = new OvenSchedulingProblem(optimizer);
model.ReadInstance(inputFile);
model.PreprocessData();
model.Solve(timeLimit);
model.WriteSolution(outputFile);
}
}
catch (Exception ex)
{
Console.Error.WriteLine(ex);
Environment.Exit(1);
}
}
}
- Compilation / Execution (Windows)
-
javac OvenShedulingProblem.java -cp %HX_HOME%\bin\hexaly.jarjava -cp %HX_HOME%\bin\hexaly.jar;. OvenShedulingProblem instances\21-n25-k2-a2.dat
- Compilation / Execution (Linux)
-
javac OvenShedulingProblem.java -cp /opt/hexaly_15_0/bin/hexaly.jarjava -cp /opt/hexaly_15_0/bin/hexaly.jar:. OvenShedulingProblem instances/21-n25-k2-a2.dat
// Copyright (c) Hexaly. Permission is hereby granted to use, copy,
// and modify this code for applications developed with Hexaly.
import java.io.*;
import java.util.*;
import com.hexaly.optimizer.*;
public class OvenSchedulingProblem {
private final HexalyOptimizer optimizer;
private int horizon;
private int nbAttributes;
// Attribute 0 is reserved for empty batches
private final int emptyAttribute = 0;
private int nbMachines;
private int nbAvailabilities;
private int nbJobs;
private int nbMaxBatch;
private int nbTotalBatch;
private long[][] setupCostsMatrix;
private long[][] setupTimesMatrix;
private long[] machineMinCapacity;
private long[] machineMaxCapacity;
private int[] machineInitialAttribute;
private int[][] availabilityStart;
private int[][] availabilityEnd;
private boolean[][] machineEligibility;
private long[] jobReleaseDate;
private long[] jobDueDate;
private long[] jobMinProcessingTime;
private long[] jobMaxProcessingTime;
private long[] jobSize;
private int[] jobAttribute;
private long upperBoundIntegerObjective;
private long weightBatchProcessingTime;
private long weightTardyJobs;
private long weightSetupTimes;
private long weightSetupCosts;
private long[][] availabilityDense;
private HxExpression[] batchContent;
private HxExpression[] batchInterval;
private HxExpression[][] machineBatchContent;
private HxExpression[][] machineBatchInterval;
private HxExpression[][] machineBatchSize;
private HxExpression[][] machineBatchUsed;
private HxExpression[][] machineBatchType;
private HxExpression[] jobIndex;
private HxExpression[] jobInterval;
private HxExpression batchProcessingTime;
private HxExpression tardyJobs;
private HxExpression setupCosts;
private HxExpression setupTimes;
private HxExpression objective;
private OvenSchedulingProblem(HexalyOptimizer optimizer) {
this.optimizer = optimizer;
}
private static final class IntReader implements Closeable {
private final Scanner scanner;
IntReader(String fileName) throws FileNotFoundException {
scanner = new Scanner(new File(fileName));
}
int nextInt() {
return scanner.nextInt();
}
long nextLong() {
return scanner.nextLong();
}
@Override
public void close() {
scanner.close();
}
}
/* Read instance data from the input file */
private void readInstance(String fileName) throws IOException {
try (IntReader in = new IntReader(fileName)) {
horizon = in.nextInt();
nbAttributes = in.nextInt();
// Input only provides setup values for real destination attributes;
// transitions to empty batches are set to zero
setupCostsMatrix = new long[nbAttributes + 1][nbAttributes + 1];
for (int a1 = 0; a1 <= nbAttributes; ++a1) {
for (int a2 = 0; a2 <= nbAttributes; ++a2) {
if (a2 == emptyAttribute) {
setupCostsMatrix[a1][a2] = 0;
} else {
setupCostsMatrix[a1][a2] = in.nextLong();
}
}
}
setupTimesMatrix = new long[nbAttributes + 1][nbAttributes + 1];
for (int a1 = 0; a1 <= nbAttributes; ++a1) {
for (int a2 = 0; a2 <= nbAttributes; ++a2) {
if (a2 == emptyAttribute) {
setupTimesMatrix[a1][a2] = 0;
} else {
setupTimesMatrix[a1][a2] = in.nextLong();
}
}
}
nbMachines = in.nextInt();
machineMinCapacity = new long[nbMachines];
machineMaxCapacity = new long[nbMachines];
machineInitialAttribute = new int[nbMachines];
for (int m = 0; m < nbMachines; ++m) {
machineMinCapacity[m] = in.nextLong();
}
for (int m = 0; m < nbMachines; ++m) {
machineMaxCapacity[m] = in.nextLong();
}
for (int m = 0; m < nbMachines; ++m) {
machineInitialAttribute[m] = in.nextInt();
}
nbAvailabilities = in.nextInt();
availabilityStart = new int[nbMachines][nbAvailabilities];
availabilityEnd = new int[nbMachines][nbAvailabilities];
for (int m = 0; m < nbMachines; ++m) {
for (int a = 0; a < nbAvailabilities; ++a) {
availabilityStart[m][a] = in.nextInt();
}
}
for (int m = 0; m < nbMachines; ++m) {
for (int a = 0; a < nbAvailabilities; ++a) {
availabilityEnd[m][a] = in.nextInt();
}
}
nbJobs = in.nextInt();
machineEligibility = new boolean[nbJobs][nbMachines];
for (int j = 0; j < nbJobs; ++j) {
int nbEligible = in.nextInt();
for (int e = 0; e < nbEligible; ++e) {
int machineId = in.nextInt();
// The machine IDs in the input start at 1
machineEligibility[j][machineId - 1] = true;
}
}
jobReleaseDate = new long[nbJobs];
jobDueDate = new long[nbJobs];
jobMinProcessingTime = new long[nbJobs];
jobMaxProcessingTime = new long[nbJobs];
jobSize = new long[nbJobs];
jobAttribute = new int[nbJobs];
for (int j = 0; j < nbJobs; ++j)
jobReleaseDate[j] = in.nextLong();
for (int j = 0; j < nbJobs; ++j)
jobDueDate[j] = in.nextLong();
for (int j = 0; j < nbJobs; ++j)
jobMinProcessingTime[j] = in.nextLong();
for (int j = 0; j < nbJobs; ++j)
jobMaxProcessingTime[j] = in.nextLong();
for (int j = 0; j < nbJobs; ++j)
jobSize[j] = in.nextLong();
for (int j = 0; j < nbJobs; ++j)
jobAttribute[j] = in.nextInt();
upperBoundIntegerObjective = in.nextLong();
weightBatchProcessingTime = in.nextLong();
weightTardyJobs = in.nextLong();
weightSetupTimes = in.nextLong();
weightSetupCosts = in.nextLong();
}
}
/* Preprocess instance data */
private void preprocessData() {
// Create availability arrays from availability windows
availabilityDense = new long[nbMachines][horizon];
for (int m = 0; m < nbMachines; ++m) {
for (int a = 0; a < nbAvailabilities; ++a) {
int start = availabilityStart[m][a];
int end = availabilityEnd[m][a];
for (int t = start; t < end; ++t) {
if (0 <= t && t < horizon) {
availabilityDense[m][t] = 1;
}
}
}
}
// Worst case: one job per batch and per machine
nbMaxBatch = nbJobs;
nbTotalBatch = nbMachines * nbMaxBatch;
}
/* Create a step array from a dense array */
private HxExpression createStepArray(HxModel model, long[] denseArray) {
ArrayList<Long> indexes = new ArrayList<>();
ArrayList<Long> values = new ArrayList<>();
long value = denseArray[0];
for (int t = 1; t < horizon; ++t) {
if (denseArray[t] != value) {
indexes.add((long) t);
values.add(value);
value = denseArray[t];
}
}
indexes.add((long) horizon);
values.add(value);
long[] indexArray = new long[indexes.size()];
long[] valueArray = new long[values.size()];
for (int i = 0; i < indexes.size(); ++i)
indexArray[i] = indexes.get(i);
for (int i = 0; i < values.size(); ++i)
valueArray[i] = values.get(i);
return model.stepArray(model.array(indexArray), model.array(valueArray));
}
private HxExpression createMatrix(HxModel model, long[][] matrix) {
HxExpression[] rows = new HxExpression[matrix.length];
for (int i = 0; i < matrix.length; ++i) {
rows[i] = model.array(matrix[i]);
}
return model.array(rows);
}
private HxExpression createArray(HxModel model, int[] values) {
long[] longValues = new long[values.length];
for (int i = 0; i < values.length; ++i) {
longValues[i] = values[i];
}
return model.array(longValues);
}
/* Declare the optimization model */
private void solve(int timeLimit) {
HxModel model = optimizer.getModel();
HxExpression setupCostsArray = createMatrix(model, setupCostsMatrix);
HxExpression setupTimesArray = createMatrix(model, setupTimesMatrix);
HxExpression jobSizeArray = model.array(jobSize);
HxExpression jobAttributeArray = createArray(model, jobAttribute);
HxExpression jobReleaseDateArray = model.array(jobReleaseDate);
HxExpression jobDueDateArray = model.array(jobDueDate);
HxExpression jobMinProcessingTimeArray = model.array(jobMinProcessingTime);
HxExpression jobMaxProcessingTimeArray = model.array(jobMaxProcessingTime);
HxExpression machineMaxCapacityArray = model.array(machineMaxCapacity);
HxExpression machineInitialAttributeArray =
createArray(model, machineInitialAttribute);
HxExpression[] availabilities = new HxExpression[nbMachines];
// Convert availability arrays into step arrays to save space
for (int m = 0; m < nbMachines; ++m) {
availabilities[m] = createStepArray(model, availabilityDense[m]);
}
batchContent = new HxExpression[nbTotalBatch];
batchInterval = new HxExpression[nbTotalBatch];
// Set decisions: jobs assigned to each batch
for (int b = 0; b < nbTotalBatch; ++b) {
batchContent[b] = model.setVar(nbJobs);
}
// Interval decisions: time range of each batch
for (int b = 0; b < nbTotalBatch; ++b) {
batchInterval[b] = model.intervalVar(0, horizon);
}
// Each job must be assigned to exactly one batch
model.addConstraint(model.partition(batchContent));
HxExpression batchContentArray = model.array(batchContent);
HxExpression batchIntervalArray = model.array(batchInterval);
machineBatchContent = new HxExpression[nbMachines][nbMaxBatch];
machineBatchInterval = new HxExpression[nbMachines][nbMaxBatch];
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
int index = m * nbMaxBatch + b;
// View batches by machine and batch position
machineBatchContent[m][b] = batchContent[index];
// View time ranges by machine and batch position
machineBatchInterval[m][b] = batchInterval[index];
}
}
HxExpression sizeLambda = model.lambdaFunction(
j -> model.at(jobSizeArray, j));
HxExpression attributeLambda = model.lambdaFunction(
j -> model.at(jobAttributeArray, j));
machineBatchSize = new HxExpression[nbMachines][nbMaxBatch];
machineBatchUsed = new HxExpression[nbMachines][nbMaxBatch];
machineBatchType = new HxExpression[nbMachines][nbMaxBatch];
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
HxExpression content = machineBatchContent[m][b];
// Total size of each batch
machineBatchSize[m][b] = model.sum(content, sizeLambda);
// Identify non-empty batches
machineBatchUsed[m][b] = model.gt(model.count(content), 0);
// Identify common attribute of each batch
machineBatchType[m][b] = model.iif(
machineBatchUsed[m][b],
model.min(content, attributeLambda),
emptyAttribute);
}
}
jobIndex = new HxExpression[nbJobs];
jobInterval = new HxExpression[nbJobs];
for (int j = 0; j < nbJobs; ++j) {
// Batch selected for each job
jobIndex[j] = model.find(batchContentArray, j);
// Jobs in the same batch share the same time range
jobInterval[j] = model.at(batchIntervalArray, jobIndex[j]);
}
for (int j = 0; j < nbJobs; ++j) {
HxExpression interval = jobInterval[j];
// Jobs cannot start before their release date
model.addConstraint(model.geq(
model.start(interval), model.at(jobReleaseDateArray, j)));
// Batch length must satisfy each assigned job
model.addConstraint(model.geq(
model.length(interval), model.at(jobMinProcessingTimeArray, j)));
model.addConstraint(model.leq(
model.length(interval), model.at(jobMaxProcessingTimeArray, j)));
}
// Jobs can only be assigned to eligible machines
for (int j = 0; j < nbJobs; ++j) {
for (int m = 0; m < nbMachines; ++m) {
if (!machineEligibility[j][m]) {
for (int b = 0; b < nbMaxBatch; ++b) {
model.addConstraint(model.not(
model.contains(machineBatchContent[m][b], j)));
}
}
}
}
// Each batch must consist of jobs with the same type
for (int b = 0; b < nbTotalBatch; ++b) {
model.addConstraint(model.leq(model.count(
model.distinct(batchContent[b], attributeLambda)), 1));
}
// Batch size cannot exceed the machine capacity
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
model.addConstraint(model.leq(machineBatchSize[m][b],
model.at(machineMaxCapacityArray, m)));
}
}
// Non-overlap between batches, with sequence-dependent setup times
for (int m = 0; m < nbMachines; ++m) {
for (int b = 1; b < nbMaxBatch; ++b) {
HxExpression prevAttribute = machineBatchType[m][b - 1];
HxExpression nextAttribute = machineBatchType[m][b];
HxExpression setupTime = model.at(setupTimesArray,
prevAttribute, nextAttribute);
model.addConstraint(model.leq(
model.sum(model.end(machineBatchInterval[m][b - 1]), setupTime),
model.start(machineBatchInterval[m][b])));
// Empty batches must be last to keep setups between non-empty batches
model.addConstraint(model.geq(
machineBatchUsed[m][b - 1], machineBatchUsed[m][b]));
}
}
// Account for the setup time before the first batch for each machine
for (int m = 0; m < nbMachines; ++m) {
HxExpression setupTime = model.at(
setupTimesArray,
model.at(machineInitialAttributeArray, m),
machineBatchType[m][0]);
model.addConstraint(model.geq(
model.start(machineBatchInterval[m][0]), setupTime));
}
// Setup costs between each batch
HxExpression[] machineSetupCosts = new HxExpression[nbMachines];
for (int m = 0; m < nbMachines; ++m) {
HxExpression sum = model.sum();
for (int b = 1; b < nbMaxBatch; ++b) {
HxExpression prevAttribute = machineBatchType[m][b - 1];
HxExpression nextAttribute = machineBatchType[m][b];
sum.addOperand(model.at(setupCostsArray,
prevAttribute, nextAttribute));
}
machineSetupCosts[m] = sum;
}
// Setup times between each batch
HxExpression[] machineSetupTimes = new HxExpression[nbMachines];
for (int m = 0; m < nbMachines; ++m) {
HxExpression sum = model.sum();
for (int b = 1; b < nbMaxBatch; ++b) {
HxExpression prevAttribute = machineBatchType[m][b - 1];
HxExpression nextAttribute = machineBatchType[m][b];
sum.addOperand(model.at(setupTimesArray,
prevAttribute, nextAttribute));
}
machineSetupTimes[m] = sum;
}
for (int m = 0; m < nbMachines; ++m) {
final int machine = m;
HxExpression availabilityLambda = model.lambdaFunction(
t -> model.at(availabilities[machine], t));
for (int b = 0; b < nbMaxBatch; ++b) {
HxExpression next = machineBatchInterval[m][b];
HxExpression prevAttribute = b == 0
? model.createConstant(emptyAttribute)
: machineBatchType[m][b - 1];
HxExpression nextAttribute = machineBatchType[m][b];
HxExpression setupTime = model.at(setupTimesArray,
prevAttribute, nextAttribute);
// Setup and processing must fit in a single machine availability
model.addConstraint(
model.geq(
model.min(model.range(
model.sub(model.start(next), setupTime),
model.end(next)),
availabilityLambda),
1));
}
}
// Total batch processing time
HxExpression processingSum = model.sum();
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
processingSum.addOperand(model.prod(
machineBatchUsed[m][b],
model.length(machineBatchInterval[m][b])));
}
}
batchProcessingTime = processingSum;
// Number of tardy jobs
HxExpression tardySum = model.sum();
for (int j = 0; j < nbJobs; ++j) {
tardySum.addOperand(model.gt(
model.end(jobInterval[j]), model.at(jobDueDateArray, j)));
}
tardyJobs = tardySum;
// Total setup costs
setupCosts = model.sum(machineSetupCosts);
// Total setup times
setupTimes = model.sum(machineSetupTimes);
// Minimize weighted processing time, tardy jobs, and setup costs
objective = model.sum(
model.prod(weightBatchProcessingTime, batchProcessingTime),
model.prod(weightTardyJobs, tardyJobs),
model.prod(weightSetupCosts, setupCosts),
model.prod(weightSetupTimes, setupTimes));
model.minimize(objective);
model.close();
/* Parameterize the solver */
optimizer.getParam().setTimeLimit(timeLimit);
optimizer.solve();
}
private ArrayList<Integer> jobsInBatch(int m, int b) {
ArrayList<Integer> jobs = new ArrayList<>();
HxCollection collection = machineBatchContent[m][b].getCollectionValue();
for (Long value : collection) {
jobs.add(value.intValue());
}
return jobs;
}
/* Write the solution in a file */
private void writeSolution(String fileName) throws IOException {
if (fileName == null)
return;
try (PrintWriter output = new PrintWriter(fileName)) {
output.println("Objective: " + objective.getIntValue());
output.println("Machine Start End Jobs");
for (int m = 0; m < nbMachines; ++m) {
for (int b = 0; b < nbMaxBatch; ++b) {
if (machineBatchUsed[m][b].getIntValue() == 0)
continue;
HxInterval interval =
machineBatchInterval[m][b].getIntervalValue();
ArrayList<Integer> jobs = jobsInBatch(m, b);
output.print(
"Machine: " + (m + 1)
+ " | Start: " + interval.getStart()
+ " | End: " + interval.getEnd()
+ " | Jobs: ");
for (int j : jobs) {
output.print((j + 1) + " ");
}
output.println();
}
}
}
}
/* Read instance data */
public static void main(String[] args) {
String usage = "Usage: java OvenSchedulingProblem inputFile [outputFile] [timeLimit]";
if (args.length < 1) {
System.err.println(usage);
System.exit(1);
}
String inputFile = args[0];
String outputFile = args.length > 1 ? args[1] : null;
String strTimeLimit = args.length > 2 ? args[2] : "15";
int timeLimit = Integer.parseInt(strTimeLimit);
try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
OvenSchedulingProblem model = new OvenSchedulingProblem(optimizer);
model.readInstance(inputFile);
model.preprocessData();
model.solve(timeLimit);
model.writeSolution(outputFile);
} catch (Exception ex) {
System.err.println(ex);
ex.printStackTrace();
System.exit(1);
}
}
}