Morphex
Morphex

Reputation: 306

Microsoft Foundation Solver : Job Shop Scheduling issue

I am just starting using solvers, and I still have pretty much no idea what I doing but:

Lets say I have a JOB Shop Schedulling problem of sorts, and I have followed a tutorial and got a somewhat working solution, right now I am trying to expand on this:

I have a set of tasks to be done on X Resources (Machines), I want to create a schedule where a) The tasks finish as fast as possible b) and I want to minimize the time it takes to do so taking in account the Type switches.

The same machine can do different handle different types of tasks, but when switching types, there is a 1h period where the machine needs to be Setup, but I don't know how to handle this constraint, this is what I got from the tutorial.

  private void InitializeGoal()
        {
            Goal goal = model.AddGoal("goal", GoalKind.Minimize, makespan); // (34)

        }

        /// <summary>Create the model.
        /// </summary>
        /// <param name="project">The project to be scheduled.</param>
        public void Initialize(Project project)
        {
            context = SolverContext.GetContext();
            context.ClearModel();
            model = context.CreateModel();

            int eventCount = project.Tasks.Count;

            // we will fill these in in the remainder of the post.
            InitializeSets(project.Tasks.Count, eventCount, project.Resources.Count);
            InitializeParameters(project.Tasks, project.Resources);
            InitializeDecisions();
            InitializeGoal();
            InitializeConstraints(project, eventCount);
        }

        private void InitializeSets(int taskCount, int eventCount, int resourceCount)
        {
            tasks = new Set(Domain.Real, "tasks");
            events = new Set(0, eventCount, 1);
            events1ToN = new Set(1, eventCount, 1); // starting from event 1.
        }

        private void InitializeParameters(ICollection<Task> t, ICollection<Resource> r)
        {
            entrega = new Parameter(Domain.Integer, "entrega", tasks);
            entrega.SetBinding(t, "Entrega", "ID");
            molde = new Parameter(Domain.Integer, "molde", tasks);
            molde.SetBinding(t, "Molde", "ID");
            duration = new Parameter(Domain.RealNonnegative, "duration", tasks);
            duration.SetBinding(t, "Duration", "ID");
            model.AddParameters(duration,molde,entrega);
        }

        private void InitializeDecisions()
        {
            makespan = new Decision(Domain.RealNonnegative, "makespan");
            isActive = new Decision(Domain.IntegerRange(0, 1), "isActive", tasks, events);
            start = new Decision(Domain.RealNonnegative, "start", events);

            modelSwitch = new Decision(Domain.Boolean, "modelSwitch", tasks);

            model.AddDecisions(makespan, isActive, start, modelSwitch);
        }

        private void InitializeConstraints(Project project, int eventCount)
        {
            // Establish the makespan: the maximum finish time over all activities.
            model.AddConstraint("c35",
              Model.ForEach(events1ToN, e =>
                Model.ForEach(tasks, i =>
                  makespan >= start[e] + (isActive[i, e] - isActive[i, e - 1]) * duration[i] )
            ));

            model.AddConstraint("ValidDeliveryDate",
            Model.ForEach(tasks, e => start[e] +  duration[e] <= entrega[e]));


            // The first event starts at time 0.
            model.AddConstraint("c_36", start[0] == 0);
            // Link the isActive decision to the starts of each event and task durations.
            model.AddConstraint("c_37",
              Model.ForEach(events1ToN, e =>
                Model.ForEachWhere(events, f =>
                  Model.ForEach(tasks, i =>
                    start[f] >= start[e] + ((isActive[i, e] - isActive[i, e - 1]) - (isActive[i, f] - isActive[i, f - 1]) - 1) * duration[i]
                    ), f => f > e)));

            // Link the isActive decision with the first event. This constraint is missing in the original
            // paper.
            model.AddConstraint("c_37_e0",
              Model.ForEach(events1ToN, f =>
                Model.ForEach(tasks, i =>
                  start[f] >= start[0] + (isActive[i, 0] - (isActive[i, f] - isActive[i, f - 1]) - 1) * duration[i]
              )));

            // Order the events.
            model.AddConstraint("c_38", Model.ForEach(events1ToN, e => start[e] >= start[e - 1]));

            // Ensure adjacency of events for an in-progress task.
            SumTermBuilder sum = new SumTermBuilder(eventCount);
            for (int i = 0; i < project.Tasks.Count; i++)
            {
                for (int e = 1; e < eventCount; e++)
                {
                    sum.Add(isActive[i, e - 1]);
                    model.AddConstraint("c_39_" + i + "_" + e,
                      sum.ToTerm() <= e * (1 - (isActive[i, e] - isActive[i, e - 1])));
                }
                sum.Clear();
            }

            sum = new SumTermBuilder(eventCount);
            for (int i = 0; i < project.Tasks.Count; i++)
            {
                for (int e = 1; e < eventCount; e++)
                {
                    for (int e1 = e; e1 < eventCount; e1++)
                    {
                        sum.Add(isActive[i, e1]); // (it's inefficient to reconstruct this for each value of e.)
                    }
                    model.AddConstraint("c_40_" + i + "_" + e,
                      sum.ToTerm() <= e * (1 + (isActive[i, e] - isActive[i, e - 1])));
                    sum.Clear();
                }
            }

            // All activities must be active during the project.
            model.AddConstraint("c_41", Model.ForEach(tasks, i =>
              Model.Sum(Model.ForEach(events, e => isActive[i, e])) >= 1));

            // A link (i, j) means that the start of task j must be after the finish of task i.
            int c42 = 0;
            foreach (TaskDependency link in project.Dependencies)
            {
                int i = link.Source.ID;
                int j = link.Destination.ID;
                sum = new SumTermBuilder(eventCount);
                for (int e = 0; e < eventCount; e++)
                {
                    sum.Add(isActive[j, e]); // sum now has isActive[j, 0] .. isActive[j, e].
                    model.AddConstraint("c_42_" + c42++, isActive[i, e] + sum.ToTerm() <= 1 + e * (1 - isActive[i, e]));
                }
            }

            // Resource usage during each event must not exceed resource capacity.
            Dictionary<Resource, int> resToId = new Dictionary<Resource, int>(project.Resources.Count);
            for (int k = 0; k < project.Resources.Count; k++)
            {
                resToId[project.Resources[k]] = k;
            }
            SumTermBuilder[] totalResWork = new SumTermBuilder[project.Resources.Count];
            int c43 = 0;
            for (int e = 0; e < eventCount; e++)
            {
                for (int taskID = 0; taskID < project.Tasks.Count; taskID++)
                {
                    foreach (var assn in project.Tasks[taskID].Assignments)
                    {
                        int resID = resToId[assn.Resource];
                        if (totalResWork[resID] == null)
                        {
                            totalResWork[resID] = new SumTermBuilder(5); // most tasks will have <= 4 assignments.
                        }
                        totalResWork[resID].Add(assn.Units * isActive[taskID, e]);
                    }
                }

                for (int resID = 0; resID < totalResWork.Length; resID++)
                {
                    if (totalResWork[resID] != null)
                    {
                        model.AddConstraint("c43_" + c43++, totalResWork[resID].ToTerm() <= project.Resources[resID].MaxUnits);
                        totalResWork[resID] = null; // note: memory churn...
                    }
                }
            }
        }

I have added the constraint to validate that the task is finished before the delivery data (entrega in this case):

    model.AddConstraint("ValidDeliveryDate",
    Model.ForEach(tasks, e => start[e] +  duration[e] <= entrega[e]));

It seems to work fine with this, but now I want to take in account the tasks Molde (Aka type), basically, I want to reduce the number of switches between tasks types and the time it takes to finish this.

I assumed the fastest way was to change the task duration to accommodate the switch time, but I am clueless on how/where to do that.

I really noobie on all this solver/optimization problems, but project came up where this could be useful, so any insight/explanation is greatly appreciated.

EDIT: I thought of a possible solution that is to add a constraint that enforces that on two consecutive tasks, if the Molde variables changes a 1h gap is introduced, but I also have no idea how this would be implemented.

Upvotes: 0

Views: 448

Answers (0)

Related Questions