Microsoft Solver Foundation could not solve my model in some cases

Question

I'm working on a production planning project, so I want to find an order production start time in some machines(A, B).

For simplification purpose, I suppose that I have 2 machines(machine A and machine B) I have following constraints:

• Each machine can work on some times of day only (A_TimeLimitation, B_TimeLimitation) for simplification purpose I supposed that

  • machine A can work in following ranges:

    (2014/12/4 00:00:00 - 2014/12/4 02:00:00) or (2014/12/4 04:00:00 - 2014/12/4 06:00:00)

  • machine B can work in following ranges:

    (2014/12/4 02:00:00 - 2014/12/4 04:00:00) or (2014/12/4 05:00:00 - 2014/12/4 07:00:00)

• Each product must go through machine A and then machine B.

• Each product take some times in each machine (60 minutes in my sample).
• Machine B should be start after machine A finished it's work.
• B can start working, at most 10 minutes after A finished its work. [Updated]
• The goal is to minimize the order production time.

I used following code to convert a DateTime to minutes:

var minutes = new TimeSpan(dateTime.Ticks).TotalMinutes;

So using above code my DateTime ranges converted to Double ranges.

I'm using Microsoft Solver Foundation to solve the problem, so I used following code:

var context = SolverContext.GetContext();
var model   = context.CreateModel();
var a_OperationTime = 60;
var b_OperationTime = 60;
var tolerance = 10;

//Decision
Decision A_StartTime = new Decision(Domain.IntegerNonnegative, "A_StartTime");
model.AddDecision(A_StartTime);
Decision B_StartTime = new Decision(Domain.IntegerNonnegative, "B_StartTime");
model.AddDecision(B_StartTime);

 //Constraints
model.AddConstraint("A_TimeLimitations" ,
                 (1059220800 <= A_StartTime <= 1059220860) | 
                 (1059221160 <= A_StartTime <= 1059221220));

model.AddConstraint("B_TimeLimitations" , 
                 (1059220920 <= B_StartTime <= 1059220980) | 
                 (1059221100 <= B_StartTime <= 1059221160));
model.AddConstraint("B_ContiguousLimitations" , 
                 B_StartTime - (A_StartTime + 60) <= tolerence);

//Goal
var A_StartTime = model.Decisions.First(x => x.Name == "A_StartTime");
var B_StartTime = model.Decisions.First(x => x.Name == "B_StartTime");
model.AddGoals("OrderDuration", GoalKind.Minimize, B_StartTime - A_StartTime);

//Solve
var directive = new ConstraintProgrammingDirective();
//directive.TimeLimit = 10000;
var solution = context.Solve(directive);

But when I run the code it seems to go into an infinite loop, when I specify TimeLimit for my directive, after 10000 milliseconds, solution.Quality is Unknown that it means MSF could not find any solution, if I remove second DateTime range in machine A the code can find a solution.

Does anyone know where is the problem?

Answer 1

I found the problems

1. I should define more constraints in my model
2. My time limits was very large, I change DateTimes to double converting method with hankank guidance

So the final solution is here:

//extention method for converting DateTime to normalized double
public static double ToMinutes(this DateTime value)
{
   return (value-new DateTime(2014, 12, 3)).TotalMinutes;
}

var a1_start = new DateTime(2014, 12, 4).ToMinutes();
var a1_finish = new DateTime(2014, 12, 4, 2, 0, 0).ToMinutes();
var a2_start = new DateTime(2014, 12, 4, 4, 0, 0).ToMinutes();
var a2_finish = new DateTime(2014, 12, 4, 6, 0, 0).ToMinutes();
var b1_start = new DateTime(2014, 12, 4,1,0,0).ToMinutes();
var b1_finish = new DateTime(2014, 12, 4, 1, 55, 0).ToMinutes();
var B2_start = new DateTime(2014, 12, 4, 5, 0, 0).ToMinutes();
var B2_finish = new DateTime(2014, 12, 4, 6, 0, 0).ToMinutes();

var context = SolverContext.GetContext();
var model = context.CreateModel();
var a_OperationTime = 60;
var b_OperationTime = 60;
var tolerance = 10;

//Decision
Decision A_StartTime = new Decision(Domain.IntegerNonnegative,"A_StartTime");
model.AddDecision(A_StartTime);
Decision B_StartTime = new Decision(Domain.IntegerNonnegative,"B_StartTime");
model.AddDecision(B_StartTime);

//Constraints
model.AddConstraint("A_TimeLimitations",
                        ((a1_start <= A_StartTime <= a1_finish) & 
                         (a1_start + 60 <= A_StartTime + 60 <= a1_finish)) |
                        ((a2_start <= A_StartTime <= a2_finish) & 
                         (a2_start + 60 <= A_StartTime + 60 <= a2_finish)));

model.AddConstraint("B_TimeLimitations",
                       ((b1_start <= B_StartTime <= b1_finish) & 
                        ((b1_start + 60 <= B_StartTime + 60 <= b1_finish))) |
                       ((B2_start <= B_StartTime <= B2_finish) & 
                        (B2_start + 60 <= B_StartTime + 60 <= B2_finish)));
model.AddConstraint("B_ContiguousLimitations",
                          B_StartTime - (A_StartTime + 60) <= tolerance);

model.AddConstraint("B_GreaterThan_A",
                     B_StartTime >= A_StartTime + 60);
//Goal
A_StartTime = model.Decisions.First(x => x.Name == "A_StartTime");
B_StartTime = model.Decisions.First(x => x.Name == "B_StartTime");
model.AddGoals("OrderDuration",GoalKind.Minimize, B_StartTime - A_StartTime);

//Solve
var directive = new ConstraintProgrammingDirective();
var solution = context.Solve(directive);