Originally posted by: Zoubeir

I have a scheduling problem formulated as an integer linear program (ILP). I am using JuliaLang and JuMP to model the problem. I use CPLEX solver to solve this problem. Some of the problem parameter is the number of machines m. When I run the solver, for example, for m=2,3,4,..., I encounter no problem and the time to finish solving the problem is very reasonable. However, for m=1, CPLEX takes long time to finish and the CPU usage is 100% (in windows task manager). What is the most closely related cause of this? How can I fix it?

The fact that the slowdown occurs with m=1 suggests that perhaps it is very hard to schedule your jobs with just a single machine (nothing to do with CPLEX). As for fixing it, without knowing details of the model (and, trust me, I'm not asking for them) there's no way to say. Possibly the problem is intrinsically hard with one machine and nothing can be done about it. Possibly there is something about your formulation that could be done better with a different formulation. Maybe the best thing to do with m=1 is to skip the model, enumerate all possible solutions and pick a winner.

Originally posted by: Zoubeir

I think you are right. What confuses me is that if the problem is hard for m=1, then it must also be hard for any m>1. But I like your suggestion of enumerating all possible solutions and picking a winner. I thought of looking for a way to see where CPLEX is stuck (like, maybe, it is going in some loop without getting improvements, or it is stuck in the branching operation.) Maybe if I can see where it is stuck, I can understand the problem?

The node log (for m=1) may give some hints. If CPLEX takes a very long time to find the first feasible solution, then quite possibly the presence of only a single machine "chokes" the system. In that case, using a heuristic to find a good initial feasible solution and seeding CPLEX with that solution might help. On the other hand, if the initial solution appears early but is quite bad, and improved solutions show up later, possibly you could expedite the search by specifying branching priorities (assuming you have some idea what a good solution should look like, for instance which jobs should go early in the sequence). If a near-optimal solution shows up quickly but the bound converges slowly (not something I would necessarily associate with using a single machine, but maybe), you could try changing the MIP emphasis switch to the setting that stresses improving the bound.