Production Scheduling with Stock- and Staff-Related Restrictions

Abstract

Effective production scheduling allows manufacturing companies to be flexible and well-adjusted to varying customer demand. In practice, production scheduling decisions are subject to several complex constraints which emerge from staff working hours and skills, delivery schedules, stock capacities, machine maintenance and machine setup. This paper introduces a novel production scheduling problem based on the real-world case of a manufacturing company in Belgium. Given a set of customer requests which may only be delivered together on one of the provided potential shipment days, the problem is to select a subset of these requests and schedule the production of the required item quantities subject to the aforementioned restrictions. All decisions must be taken for a time horizon of several days, leading to a complex problem where there may not be enough resources to serve all requests. We provide an integer programming formulation of this novel problem which is capable of solving small-scale instances to proven optimality. In order to efficiently solve large-scale instances, we develop a metaheuristic algorithm. A computational study with instances generated from real-world data indicates that the metaheuristic can quickly produce high-quality solutions, even for cases comprising several days, requests and limited stock capacities. We also conduct a sensitivity analysis concerning characteristics of the schedules and instances, the results of which can be exploited to increase production capacity and revenue.

Appendix A Integer Linear Programming Formulation

To model the PSP as an ILP we introduce some additional notation.

• T: set of all blocks in the scheduling horizon: $T=\{1,\ldots ,|B|,|B|+1,\ldots ,2|B|,2|B|+1,\ldots ,|D||B|\}$

• $T^M\subset T$: set of all maintenance blocks.

• $T^N\subset T$: set of all night-shift blocks.

• $T^O\subset T^N$: set of all overtime blocks.

• $T_r\subset T$: set of all shipping blocks for request $r\in R$.

• $d(t)\in D$: the day index of block $t\in T$: $d(t)=1$ for $t=1,\ldots ,|B|$; $d(t)=2$ for $t=|B|+1,\ldots ,2|B|$ ...

• $h_n$: the index of the last day with a night shift pushed from the previous scheduling horizon.

• $g_0^m$: at the beginning of current scheduling horizon, the number of days passed without a maintenance for machine $m\in M$ since the last maintenance in the previous scheduling horizon.

• $b_n^d$: the last block of day $d\in D$.

Additionally, a set of decision variables is used.

• $\eta _{d}=1$ if there is a night shift on day $d\in D$, 0 otherwise.

• $\pi _{d}=1$ if there is parallel processing of machines on day $d\in D$, 0 otherwise.

• $\theta _{t}=1$ if block $t\in T^O$ is used as overtime, 0 otherwise.

• $y_{t}^m=1$ if machine $m\in M$ is idle during block $t\in T$, 0 otherwise.

• $\mu _{t}^m=1$ if $m\in M$ is under maintenance during block $t\in T$, 0 otherwise.

• $\gamma _{r}^t=1$ if request $r\in R$ is fulfilled by shipping at $t\in T_r$, 0 otherwise.

• $z_{ti}^m=1$ if $m\in M$ is producing item $i\in I$ during block $t\in T$, 0 otherwise.

• $\varDelta _{id}$ is the stock level of item $i\in I$ at the end of day $d\in D$. $\varDelta _{i0}$ is the initial stock of i.

• $\phi _{id}$ is the stock deficit of $i\in I$ at the end of day $d\in D$.

• $\tau _{d}^m=1$ if $m\in M$ undergoes a maintenance on day $d\in D$, 0 otherwise.

• $v_{tt'}^{m}=1$ if during block $t\in T^M$, machine $m\in M$ is occupied by a long setup to be finished during block $t'\in T^M$, 0 otherwise.

• $w_{ij}^{mt'}=1$ if during block $t'\in T^M$, machine $m\in M$ is occupied and finished a long setup from item $i\in I$ to item $j\in I$, 0 otherwise.

• $\psi _{tt'}^{m}=1$ if during block $t\in T$, machine $m\in M$ is occupied by a short setup to be finished during block $t'\in T$, 0 otherwise.

• $u_{ij}^{mt}=1$ if during block $t\in T$, machine $m\in M$ is occupied and finished a short setup from item $i\in I$ to item $j\in I$, 0 otherwise.

• $\rho _{ti}^m=1$ if machine $m\in M$ is set-up to produce item $i\in I$ during block $t\in T$, 0 otherwise ($\rho _{0i}^m=1$ if the initial configuration of machine m is for item i).

The following is an integer programming formulation for the PSP.

$$\begin{aligned} \min \,\, \sum _{r\in R}\sum _{t\in T_r}c(r)(1-\gamma _{r}^t) + \sum _{t\in T^O}p_o\theta _t + \sum _{d\in D}(p_p\pi _d + p_n\eta _d + \sum _{i\in I}p_s\phi _{id}) \end{aligned}$$

(1)

$$\begin{aligned} \text{ s.t. }&\theta _t + \eta _{d(t)}\le 1,&\forall t\in T^O, \end{aligned}$$

(2)

$$\begin{aligned}&\theta _{t+1} \le \theta _t,&\forall t\in T^O, \end{aligned}$$

(3)

$$\begin{aligned}&\theta _t + \eta _{d(t)} +y_t^m \ge 1,&\forall t\in T^O, m \in M \end{aligned}$$

(4)

$$\begin{aligned}&\eta _{d(t)} +y_t^m \ge 1,&\forall t\in T^N\setminus T^O, m \in M \end{aligned}$$

(5)

$$\begin{aligned}&(d_n-1)\eta _{d} \le \sum _{d'=d+1}^{d+d_n-1}\eta _{d'} +(d_n-1)\eta _{d-1},&\forall d:|D|-d_n\ge d>h_n \end{aligned}$$

(6)

$$\begin{aligned}&(d_n-1)\eta _{d} \le \sum _{d'=d-d_n+1}^{d-1}\eta _{d'} +(d_n-1)\eta _{d+1},&\forall d\ge \max \{h_n+1,d_n\} \end{aligned}$$

(7)

$$\begin{aligned}&y_t^m+\sum _{i\in I}z_{ti}^m+\sum _{t'\in T:t'\ge t}\psi _{tt'}^{m} +\sum _{t'\in T^M:t'\ge t}v_{tt'}^{m}+\mu _t^m = 1,&\forall t\in T^M, m\in M \end{aligned}$$

(8)

$$\begin{aligned}&y_t^m+\sum _{i\in I}z_{ti}^m+\sum _{t'\in T:t'\ge t}\psi _{tt'}^{m} = 1,&\forall t\in T\setminus T^M, m\in M \end{aligned}$$

(9)

$$\begin{aligned}&\sum _{m\in M}(1-y_t^m) \le (|M|-1)\pi _d + 1,&\forall d\in D,t\in T\setminus T^N:d(t)=d \end{aligned}$$

(10)

$$\begin{aligned}&\varDelta _{id}=\varDelta _{id-1}+\sum _{t\in T:d(t)=d}\sum _{m\in M}e_{i}^mz_{ti}^m-\sum _{r\in R}q_r^i\gamma _r^{t'},&\forall d\in D, i\in I, t'=b_n^d \end{aligned}$$

(11)

$$\begin{aligned}&\phi _{id}\ge S_i^{min} - \varDelta _{id},&\forall d\in D, i\in I \end{aligned}$$

(12)

$$\begin{aligned}&\sum _{t\in T_r}\gamma _r^{t'}\le 1,&\forall r\in R, i\in I \end{aligned}$$

(13)

$$\begin{aligned}&u_{ij}^{mt}\le \psi _{tt}^m,&\forall t\in T, m\in M, (i,j)\in U \end{aligned}$$

(14)

$$\begin{aligned}&(s_{ij}^m-1)u_{ij}^{mt'}\le \sum _{t \in T:d(t)=d(t'),t < t'}\psi _{tt'}^m,&\forall t'\in T, m\in M, (i,j)\in U \end{aligned}$$

(15)

$$\begin{aligned}&\sum _{t^3\in T:t^3\ge t,t^3\ne t^2}\psi _{tt^3}^m+\sum _{t^3\in T^M:t^3\ge t}v_{tt^3}^{m}+\sum _{i\in I}z_{ti}^m+\psi _{t^1t^2}^m\!\le 1,&\forall t,t^1,t^2\!\in T\!:\!t^1\!\le \! t\le t^2, m\!\in \! M \end{aligned}$$

(16)

$$\begin{aligned}&\sum _{t \in T : d(t) = d} u_{ij}^{mt} \le 1,&\forall d \in D, m \in M, (i,j) \in U \end{aligned}$$

(17)

$$\begin{aligned}&w_{ij}^{mt}\le v_{tt}^m,&\forall t\in T^M, m\in M, (i,j)\in L \end{aligned}$$

(18)

$$\begin{aligned}&(s_{ij}^m-1)w_{ij}^{mt'}\le \sum _{t\in T^M:d(t)=d(t')}^{t'-1}v_{tt'}^m,&\forall t'\in T^M, m\in M,(i,j)\in L \end{aligned}$$

(19)

$$\begin{aligned}&\sum _{t^3\in T^M:t^3\ge t,t^3\ne t^2}v_{tt^3}^m+\sum _{t^3\in T:t^3\ge t}\psi _{tt^3}^{m}+\sum _{i\in I}z_{ti}^m+v_{t^1t^2}^m\!\le \! 1,&\forall t,t^1,t^2\in T^M\!\!:\!t^1\!\le \! t\!\le \!t^2, m\!\in \! M \end{aligned}$$

(20)

$$\begin{aligned}&\sum _{t \in T : d(t) = d} w_{ij}^{mt} \le 1,&\forall d \in D, m \in M, (i,j) \in L \end{aligned}$$

(21)

$$\begin{aligned}&\sum _{m\in M}\sum _{t'\in T^M:t'\ge t}v_{tt'}^{m}+\sum _{m\in M}\mu _t^m\le 1,&\forall t\in T^M \end{aligned}$$

(22)

$$\begin{aligned}&\sum _{t:d(t)=d}\mu _t^m =f^m\tau ^{m}_d,&\forall d\in D, m\in M \end{aligned}$$

(23)

$$\begin{aligned}&\sum _{d=0}^{g^m_{max}-d_0^m}\tau _d^m \ge 1,&\forall m\in M \end{aligned}$$

(24)

$$\begin{aligned}&\sum _{d'=d-g^m_{max}}^{d}\tau _d^m \ge 1,&\forall d\in D:d\ge g^m_{max}, m\in M \end{aligned}$$

(25)

$$\begin{aligned}&\mu _{t^1}^m+\mu _{t^2}^m + \sum _{i\in I}z_{ti}^m \le 2,&\forall t,t^1,t^2\in T^M, m\in M\nonumber \\&t^1\le t\le t^2, d(t^1)=d(t^2) \end{aligned}$$

(26)

$$\begin{aligned}&z_{ti}^m\le \rho _{ti}^m,&\forall t\in T, m\in M, i\in I \end{aligned}$$

(27)

$$\begin{aligned}&\sum _{i\in I}\rho _{ti}^m\le 1,&\forall t\in T, m\in M \end{aligned}$$

(28)

$$\begin{aligned}&\rho _{ti}^m \le \rho _{(t-1)i}^m+\sum _{j:(j,i)\in U}u_{ji}^{mt-1}+\sum _{j:(j,i)\in L}w_{ji}^{mt-1},&\forall t\in T^M, m\in M, i\in I \end{aligned}$$

(29)

$$\begin{aligned}&\rho _{ti}^m \le \rho _{(t-1)i}^m+\sum _{j:(j,i)\in U}u_{ji}^{mt-1},&\forall t\in T\setminus T^M, m\in M, i\in I \end{aligned}$$

(30)

$$\begin{aligned}&\sum _{j:(i,j)\in U}u_{ij}^{mt}+\sum _{j:(i,j)\in L}w_{ij}^{mt}\le \rho _{(t-1)i}^m,&\forall t\in T^M, m\in M, i\in I \end{aligned}$$

(31)

$$\begin{aligned}&\sum _{j:(i,j)\in U}u_{ij}^{mt}\le \rho _{(t-1)i}^m,&\forall t\in T\setminus T^M, m\in M, i\in I \end{aligned}$$

(32)

$$\begin{aligned}&\varDelta _{id}\le S_i^{max},&\forall d\in D, i\in I \end{aligned}$$

(33)

$$\begin{aligned}&\phi _{id}, \varDelta _{id} \ge 0,&\forall d\in D, i\in I \end{aligned}$$

(34)

$$\begin{aligned}&\eta _{d}, \pi _{d}\in \{0,1\},&\forall d\in D \end{aligned}$$

(35)

$$\begin{aligned}&\tau _{d}^m \in \{0,1\},&\forall d\in D, m\in M \end{aligned}$$

(36)

$$\begin{aligned}&\theta _t \in \{0,1\},&\forall t\in T^O \end{aligned}$$

(37)

$$\begin{aligned}&y_t^m\in \{0,1\},&\forall t\in T\end{aligned}$$

(38)

$$\begin{aligned}&\mu _t^m\in \{0,1\},&\forall t\in T^M \end{aligned}$$

(39)

$$\begin{aligned}&z_{ti}^m, \rho _{ti}^m\in \{0,1\},&\forall t\in T, i\in I,m\in M \end{aligned}$$

(40)

$$\begin{aligned}&u_{ij}^{mt}\in \{0,1\},&\forall t\in T, (i,j)\in U,m\in M \end{aligned}$$

(41)

$$\begin{aligned}&w_{ij}^{mt}\in \{0,1\},&\forall t\in T^M, (i,j)\in L,m\in M \end{aligned}$$

(42)

$$\begin{aligned}&v_{tt'}^{m}\in \{0,1\},&\forall t,t'\in T^M:t'\ge t, m\in M \end{aligned}$$

(43)

$$\begin{aligned}&\gamma _{r}^{t}\in \{0,1\},&\forall r\in R, t\in T_r \end{aligned}$$

(44)

Objective function (1) minimizes the sum of revenue loss from unserved requests, additional personnel costs (overtime, night shift and parallel operations) and penalties incurred by stock deficits. Constraints (2) ensure that if a block is used for overtime then there is no night shift that day and vice versa (meaning no overtime is possible if there is a night shift on a certain day). Constraints (3) forbid using isolated overtime blocks, in other words: overtime in a block is possible only if the previous overtime block is also used, except for the first overtime block, which can be used without preceding overtime blocks. Constraints (4) and (5) enforce the machines to be idle during night-shift blocks if there is no overtime or night shift used that day. Constraints (6) ensure that for a certain day with no night shift on the preceding day, night shifts are only allowed if there is a night shift on every single one of the following $d_n-1$ consecutive days. Similarly, Constraints (7) ensure that for a certain day with no night shift on the following day that night shifts are only allowed if there is a night shift on every single one of the preceding $d_n-1$ consecutive days. Constraints (8) and (9) ensure that during any block, a machine is either idle or occupied by a single operation, namely: setup (short or long), maintenance or production. Constraints (10) enforce a parallel processing penalty if more than one machine is not idle. Constraints (11) are the inventory (stock) balance constraints. Constraints (12) retrieve the daily stock deficit per item, if there is any. If the inventory level is greater than the minimum stock requirement, the deficit variable assumes a value of zero thanks to the objective function (1) and binary restrictions (34). By Constraints (13), at most one shipping is conducted per request. Constraints (14)–(16) ensure that no production is performed in between the blocks of the same short setup. Constraints (18)–(20) ensure that no production is performed in between the blocks of the same long setup. Constraints (17) and (21) ensure that only one type of setup is scheduled per day. Constraints (22) ensure that at most one long setup or maintenance takes place during any single block. Constraints (23)–(26) ensure that maintenance blocks are assigned with the required frequency while ensuring that no production is conducted in between the blocks of a maintenance. Constraints (27)–(30) guarantee that production of an item is only possible if the machine has the right configuration, which is validated by a previous block either with the identical configuration or via a completed setup to that item. Maximum stock levels are respected thanks to Constraints (33). Finally, (34)–(44) are nonnegativiy and binary restrictions.