# Scheduling Problem With Identical Machines

I am working on a nonlinear scheduling problem that minimizes the electricity cost of a facility. This system includes a number of identical machines that consume power and produce a product. When the product demanded by these machines is low (i.e. near the low bound for one machine) this causes an infeasibility. I think this is occurring because in reality only one machine should be on, but the way I have the problem written, mathematically this decision is impossible to reach. In general what is the best way to model identical equipment?

I could make one machine just slightly more efficient than the other...but that's not ideal. Is there a more elegant way to handle this?

As per you mentioned, your problem divided into two parts. The first is, related to the power system optimization and the second is about machinery scheduling system. I don't know, how do you formulate the first one, (linear or non-linear) but, the second one can be represented as the mixed-integer programming as well. Also, other techniques such as CP would be useful. For scheduling your plant, some things would be considered:

• If your plant optimization problem is medium/large scale, it is convenient to use LP/MILP instead of NLP/MINLP. (defiantly, if it is possible).
• It is important to identify, which kind of machinery system you have faced? (e.g. single/parallel machine, shopping family, etc). Based on the problem in hand, you can develop an appropriate solution to that.
• If you are interested to optimize more than one objective function, for example, minimizing power-consuming versus minimizing the number of tardy jobs simultaneously, you would like to use multi-objective optimization.
• If you have encountered to probability/noisy data, the stochastic/robust optimization can be applied.

Finally, there are many related resources, software, etc which you could use them to solve your problem but, what the most important is, how do you define your problem and its specifications?

• Thank you for your thoughtful comment. The problem is currently formulated as a nonlinear program because the machine's power consumption vary's nonlinearly with production. I was trying to avoid making the problem mixed integer, but I think as you say, this is probably the most reasonable path forward. Jan 26, 2021 at 5:26

It's hard to answer this without knowing more about your model. Let's say that you have variables for the quantity produced on each machine (say, $$x_m$$ where $$m\in\lbrace 1,\dots, M\rbrace$$ indexes the machine). It sounds as if there is a nonzero lower bound $$L$$ for the output of a machine when it is running. Rather than say $$x_m \ge L\,\, \forall m$$, what you need is binary variables $$y_m$$ (1 if machine $$m$$ is used, 0 if not) with the constraint $$x_m \ge L y_m \,\, \forall m$$. Introducing binary variables makes the model harder to solve, but if you have a nonzero lower limit on output for running machines and at the same time do not require every machine to be used, I think that is unavoidable.

Also, since the machines are identical, you could arbitrarily impose the constraints $$x_1\ge x_2 \ge \dots \ge x_M$$. This would eliminate some symmetry in your model.

• I have introduced the binary variables and that did solve the problem. I was trying to avoid discontinuous variables but for now it works. I may try the prioritization that you describe above, if it can be used as a method to simplify the problem. Could you explain why it is beneficial to eliminate symmetry? Jan 26, 2021 at 5:32
• Assuming you are using some form of tree search (branch-and-bound or something similar), symmetry means functionally equivalent solutions (permutations of each other) live simultaneously in different parts of the tree. That makes it harder to prune nodes. Until a solution beats the common objective value of the various permutations, you can't prune any subtree containing at least one of them. With symmetry removed, the one legal permutation can prevent pruning one subtree but not the rest.
– prubin
Jan 26, 2021 at 18:25
• Eliminating symmetry is not 100% guaranteed to help. If a good solution has lots of "clones" scattered through the search tree, you may find it faster than if it only lives in one part of the tree. I think, though, that removing symmetry helps more often than it hurts.
– prubin
Jan 26, 2021 at 18:26
• Re the binary variables, an equivalent approach (if your solver allows it) is to define $x_m$ as semicontinuous with domain $\lbrace 0 \rbrace \cup [L, U]$ for some upper bound $U$.
– prubin
Jan 26, 2021 at 18:28