Flexible Job Shop Scheduling Problem with Sequence-Dependent Setup Times (FJSP-SDST)¶

using System;
using System.IO;
using System.Linq;
using localsolver;

public class FlexibleJobshopSetup : IDisposable
{
    // Number of jobs
    private int nbJobs;

    // Number of machines
    private int nbMachines;

    // Number of tasks
    private int nbTasks;

    // Processing time for each task, for each machine
    private long[][] taskProcessingTimeData;

    // Setup time between every two consecutive tasks, for each machine
    private int[][][] taskSetupTimeData;

    // For each job, for each operation, the corresponding task id
    private int[][] jobOperationTask;

    // Number of operations for each job;
    private int[] nbOperations;

    // Trivial upper bound for the start times of the tasks
    private long maxStart;

    // Constant for incompatible machines
    private const long INFINITE = 1000000;

    // LocalSolver
    private LocalSolver localsolver;

    // Decision variables: time range of each task
    private LSExpression[] tasks;

    // Decision variables: sequence of tasks on each machine
    private LSExpression[] jobsOrder;

    // For each task, the selected machine
    private LSExpression[] taskMachine;

    // Objective = minimize the makespan: end of the last task
    private LSExpression makespan;

    public FlexibleJobshopSetup()
    {
        localsolver = new LocalSolver();
    }

    public void ReadInstance(string fileName)
    {
        using (StreamReader input = new StreamReader(fileName))
        {
            char[] separators = new char[] { '\t', ' ' };
            string[] splitted = input
                .ReadLine()
                .Split(separators, StringSplitOptions.RemoveEmptyEntries);
            nbJobs = int.Parse(splitted[0]);
            nbMachines = int.Parse(splitted[1]);

            nbTasks = 0;
            long[][][] processingTime = new long[nbJobs][][];
            jobOperationTask = new int[nbJobs][];
            nbOperations = new int[nbJobs];
            for (int j = 0; j < nbJobs; ++j)
            {
                splitted = input
                    .ReadLine()
                    .Split(separators, StringSplitOptions.RemoveEmptyEntries);
                nbOperations[j] = int.Parse(splitted[0]);
                jobOperationTask[j] = new int[nbOperations[j]];
                processingTime[j] = new long[nbOperations[j]][];
                int k = 1;
                for (int o = 0; o < nbOperations[j]; ++o)
                {
                    int nbMachinesOperation = int.Parse(splitted[k]);
                    k++;
                    processingTime[j][o] = Enumerable.Repeat((long)INFINITE, nbMachines).ToArray();
                    for (int m = 0; m < nbMachinesOperation; ++m)
                    {
                        int machine = int.Parse(splitted[k]) - 1;
                        long time = long.Parse(splitted[k + 1]);
                        processingTime[j][o][machine] = time;
                        k += 2;
                    }
                    jobOperationTask[j][o] = nbTasks;
                    nbTasks++;
                }
            }

            input.ReadLine();
            taskSetupTimeData = new int[nbMachines][][];
            int maxSetup = 0;
            for (int m = 0; m < nbMachines; ++m)
            {
                taskSetupTimeData[m] = new int[nbTasks][];
                for (int i = 0; i < nbTasks; ++i)
                {
                    taskSetupTimeData[m][i] = new int[nbTasks];
                    splitted = input.
                        ReadLine()
                        .Split(separators, StringSplitOptions.RemoveEmptyEntries);
                    for (int j = 0; j < nbTasks; ++j)
                    {
                        taskSetupTimeData[m][i][j] = int.Parse(splitted[j]);
                        if (
                            taskSetupTimeData[m][i][j] != INFINITE
                            && taskSetupTimeData[m][i][j] > maxSetup
                        )
                            maxSetup = taskSetupTimeData[m][i][j];
                    }
                }
            }

            // Trivial upper bound for the start times of the tasks
            long maxSumProcessingTimes = 0;
            taskProcessingTimeData = new long[nbTasks][];
            for (int j = 0; j < nbJobs; ++j)
            {
                long maxProcessingTime = 0;
                for (int o = 0; o < nbOperations[j]; ++o)
                {
                    int task = jobOperationTask[j][o];
                    taskProcessingTimeData[task] = new long[nbMachines];
                    for (int m = 0; m < nbMachines; ++m)
                    {
                        taskProcessingTimeData[task][m] = processingTime[j][o][m];
                        if (
                            processingTime[j][o][m] != INFINITE
                            && processingTime[j][o][m] > maxProcessingTime
                        )
                        {
                            maxProcessingTime = processingTime[j][o][m];
                        }
                    }
                    maxSumProcessingTimes += maxProcessingTime;
                }
            }
            maxStart = maxSumProcessingTimes + nbTasks * maxSetup;
        }
    }

    public void Dispose()
    {
        localsolver.Dispose();
    }

    public void Solve(int timeLimit)
    {
        // Declare the optimization model
        LSModel model = localsolver.GetModel();

        // Sequence of tasks on each machine
        jobsOrder = new LSExpression[nbMachines];
        LSExpression machines = model.Array();
        for (int m = 0; m < nbMachines; ++m)
        {
            jobsOrder[m] = model.List(nbTasks);
            machines.AddOperand(jobsOrder[m]);
        }

        // Each task is scheduled on a machine
        model.Constraint(model.Partition(machines));

        // Only compatible machines can be selected for a task
        for (int i = 0; i < nbTasks; ++i)
        {
            for (int m = 0; m < nbMachines; ++m)
            {
                if (taskProcessingTimeData[i][m] == INFINITE)
                    model.Constraint(!model.Contains(jobsOrder[m], i));
            }
        }

        // For each task, the selected machine
        taskMachine = new LSExpression[nbTasks];
        for (int i = 0; i < nbTasks; ++i)
        {
            taskMachine[i] = model.Find(machines, i);
        }

        tasks = new LSExpression[nbTasks];
        LSExpression[] duration = new LSExpression[nbTasks];
        LSExpression taskProcessingTime = model.Array(taskProcessingTimeData);
        for (int i = 0; i < nbTasks; ++i)
        {
            // Interval decisions: time range of each task
            tasks[i] = model.Interval(0, maxStart);

            // The task duration depends on the selected machine
            LSExpression iExpr = model.CreateConstant(i);
            duration[i] = model.At(taskProcessingTime, iExpr, taskMachine[i]);
            model.Constraint(model.Length(tasks[i]) == duration[i]);
        }
        LSExpression taskArray = model.Array(tasks);

        // Precedence constraints between the operations of a job
        for (int j = 0; j < nbJobs; ++j)
        {
            for (int o = 0; o < nbOperations[j] - 1; ++o)
            {
                int i1 = jobOperationTask[j][o];
                int i2 = jobOperationTask[j][o + 1];
                model.Constraint(tasks[i1] < tasks[i2]);
            }
        }

        LSExpression taskSetupTime = model.Array(taskSetupTimeData);

        // Disjunctive resource constraints between the tasks on a machine
        for (int m = 0; m < nbMachines; ++m)
        {
            LSExpression sequence = jobsOrder[m];
            LSExpression mexpr = model.CreateConstant(m);
            LSExpression sequenceLambda = model.LambdaFunction(
                i =>
                    model.Start(taskArray[sequence[i + 1]])
                    >= (model.End(taskArray[sequence[i]])
                        + model.At(taskSetupTime, mexpr, sequence[i], sequence[i + 1])));
            model.Constraint(model.And(model.Range(0, model.Count(sequence) - 1), sequenceLambda));
        }

        // Minimize the makespan: end of the last task
        makespan = model.Max();
        for (int i = 0; i < nbTasks; ++i)
        {
            makespan.AddOperand(model.End(tasks[i]));
        }
        model.Minimize(makespan);

        model.Close();

        // Parameterize the solver
        localsolver.GetParam().SetTimeLimit(timeLimit);

        localsolver.Solve();
    }

    /* Write the solution in a file with the following format:
     *  - for each operation of each job, the selected machine, the start and end dates */
    public void WriteSolution(string fileName)
    {
        using (StreamWriter output = new StreamWriter(fileName))
        {
            Console.WriteLine("Solution written in file " + fileName);
            for (int j = 1; j <= nbJobs; ++j)
            {
                for (int o = 1; o <= nbOperations[j - 1]; ++o)
                {
                    int taskIndex = jobOperationTask[j - 1][o - 1];
                    output.WriteLine(
                        j
                            + "\t"
                            + o
                            + "\t"
                            + taskMachine[taskIndex].GetValue()
                            + "\t"
                            + tasks[taskIndex].GetIntervalValue().Start()
                            + "\t"
                            + tasks[taskIndex].GetIntervalValue().End()
                    );
                }
            }
        }
    }

    public static void Main(string[] args)
    {
        if (args.Length < 1)
        {
            Console.WriteLine("Usage: FlexibleJobshopSetup 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 (FlexibleJobshopSetup model = new FlexibleJobshopSetup())
        {
            model.ReadInstance(instanceFile);
            model.Solve(int.Parse(strTimeLimit));
            if (outputFile != null)
                model.WriteSolution(outputFile);
        }
    }
}