1

I am trying to come up with nice solution for a specific RCPSP.

Context

There is a small factory which can produce P kinds of products on N machines each machine is universal but can only create one kind of product in one setting. The machine needs some significant time to change the setting to other kind of product. Then there are C contracts which the factory must meet. A product might have dependency on another product. (for product C it is necessary to have 3 products A and 1 product B)

Most optimal solution is the one with minimal number of settings changes.

My solution

I translated the requirements in contracts to time which a machine must spent producing the product. Then split time to timespans between expedition dates of contracts.

Variables a,b,c - products a11 - time spent producing product a on machine one in timespan before first contract)

Constants A1 - time which must be spent producing product A in the first timespan E1 - first timespan (time from now to the expedition date of the first contract)

Minimize: 

f(x) = sgn a11 + sgn b11 + sgn c11 + sgn a12 + sgn b12 + sgn c12 + sgn a21 + sgn b21 + sgn c21 + sgn a22 + sgn b22 + sgn c22

Constraints:

a11 + a12 >= A1
b11 + b12 >= B1
c11 + c12 >= C1

a11 + a12 + a21 + a22 = A2
b11 + b12 + b21 + b22 = B2
c11 + c12 + c21 + c22 = C2

a11 + b11 + c11 <= E1
a12 + b12 + c12 <= E1

a21 + b21 + c21 <= E2
a22 + b22 + c22 <= E2

I don't know how to find optimal solution when my "cost" function is not linear and also I don't take into account dependencies between products.

Could you please advise me or point to relevant literature/algorithms?

jakub.petr
  • 111

1 Answers1

0

Your optimization is equivalent to the form \begin{align*} \text{min } & \sum_{j=1}^{n}\text{sign}\left(x_{j}\right)\\ \text{subject to } & A\mathbf{x}\leq\mathbf{b} \end{align*} Since there are only $n$ variables, you can split this up into $2^{n}$ linear problems by constraining $\mathbf{x}$ to lie in a particular hyperoctant of $\mathbb{R}^{n}$ (http://mathworld.wolfram.com/Hyperoctant.html).

To see how this is done, consider the simpler problem \begin{align*} \text{min } & \text{sign}\left(x_{1}\right)+\text{sign}\left(x_{2}\right)\\ \text{subject to } & A\mathbf{x}\leq \mathbf{b} \end{align*} with only two variables. This can be split up into $2^{2}=4$ problems by considering each quadrant of $\mathbb{R}^{2}$ separately:

  • $\left\{ \mathbf{x}\mid x_{1},x_{2}\geq0\right\} $
  • $\left\{ \mathbf{x}\mid x_{1},x_{2}\leq0\right\} $
  • $\left\{ \mathbf{x}\mid x_{1}\geq0,x_{2}\leq0\right\} $
  • $\left\{ \mathbf{x}\mid x_{1}\leq0,x_{2}\geq0\right\} $

Then, you have four optimal objective values; just pick whichever is lowest (note that this really becomes a task in checking whether or not there is a feasible point in each quadrant, since the objective functions are constant over each quadrant).

parsiad
  • 25,154