Initializing help system before first use

Model formulation

We are going to represent this problem by two subproblems: the machine assignment problem and the sequencing of operations on machines. The former is implemented by a MIP model; the latter is formulated as a CP (single machine) problem.

MIP model

Let COSTpm denote the production cost and DURpm the processing time of product p (p ∈ PRODS, the set of products) on machine m (m ∈ MACH, the set of machines).

To formulate the machine assignment problem we introduce binary variables usepm that take the value 1 if product p is produced on machine m and zero otherwise. The objective function is then given as

minimize
∑
p ∈ PRODS
∑
m ∈ MACH
COSTpm · usepm

The assignment constraints expressing that each order needs exactly one machine for processing it are defined as follows:

∀ p ∈ PRODS:
∑
m ∈ MACH
usepm = 1

In addition to these constraints that already fully state the problem we may define some additional constraints to strengthen the LP relaxation. All production takes place between the earliest release date and the latest due date. If we denote the length of this interval by MAX_LOAD, we may formulate the following valid inequalities expressing that the total processing time of products assigned to a machine cannot exceed MAX_LOAD:

∀ m ∈ MACH:
∑
p ∈ PRODS
DURpm · usepm ≤ MAX_LOAD

CP model

Once the set of operations assigned to machine m, ProdMachm (ProdMachm ⊆ PRODS), is known, we obtain the following sequencing problem for this machine:

∀ p ∈ ProdMachm: startp ∈ {RELp, ..., DUEp-DURpm }
∀ p, q ∈ ProdMachm, p < q: startp + DURpm ≤ startq ∨ startq + DURqm ≤ startp
Parent Topic Combining CP and MIP

© 2001-2019 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.