Scheduling of process manufacturing with setup times



Overview

The process manufacturing is (in contrast to discrete manufacturing) focused on the production of continuous goods such as oil. The planning is typically solvable by means of Linear Programming, come constraints can be introduced for MILP.

Problem Formulation

The problem consists of

  • Sequence of consecutive time intervals $ t\in\{1,\dots,n_t\}$ , each with start and end $ (s_t,e_t)$ and length $ l_t=e_t-s_t$ . Consecutive means $ e_{t}=s_{t+1}$ for all $ t\in\{1,\dots,n_t-1\}$ .
  • List of type of goods that are being produced: $ j\in \{1,…,n_j\}$
  • Demand of each type of good per time interval $ d_{j,t}$ .
  • List of production lines $ i\in{1,\dots,n_i}$
  • Availability of production lines per time interval $ a_{i,t}$ . $ a_{i,t}$ is binary – whether available or not.
  • Manufacturing speed per production line per type goods $ v_{i,j}$ .
  • Setup time of production line from one type of goods to another one $ u_{i,j,j’}$ .
  • Price for using a production line (leasing based), counted per minute $ c_{i}$

The goal is to plan the production lines so the demand is covered and the price for leasing is minimal.

Notes:

  • The setup time can be shorter or longer or equal to the length of the intervals
  • It is acceptable that the production line will not work the whole time interval if the supply has been completed sooner
  • The setup to the production of another good can start any time, not necessarily at the beginning of an interval.

Example

There are two production lines, i.e., $ n_i = 2$ and there are two types of goods, i.e. $ n_j=2$ .

We have two intervals, i.e. $ n_t=2$ , each has a leght of 1 hour. Say one starts at 1 pm, the second at 2 pm.

The demand is:

  • $ d_{1,1}=1.1$
  • $ d_{1,2}=1$
  • $ d_{2,1}=0.5$
  • $ d_{2,2}=1$

The of running the production lines are:

  • $ c_{1} =c_{2} = 1$ USD/minute

All possible setup times are twelve minutes, i.e.:

  • $ u_{i,j,j’}=0.2$ for all $ i,j,j’$ where $ j\neq j’$ .

The speeds are:

  • $ v_{1,1}=1.1$
  • $ v_{1,2}=1.5$
  • $ v_{1,1}=1$
  • $ v_{1,1}=1$

Obviously, the demand is met for a total cost of $ 4$ if the first line is producing the first type of goods at both intervals and the second line is producing the second type.

However, it might be tempting to switch them after the first interval. If there would be no setup time needed, the cost would be $ 1+1+1+0.5/1.5=3.33$ which is better. However, this is not possible because of the setup time of the second production line.

Question

What is the algorithm to schedule this manufacturing process optimally?

An answer is welcome even if it would outline the way and approach (MILP, SAT, CSP,…).

Ideas fo far

  • If the length of intervals would be fixed, say 1 hour and the setup time would be defined in terms of these units, say 2 hours. Then, it might be solvable by SAT/CSP.
  • An idea is to use an evolutionary algorithm that would: consist of a sequence of activities with mutations (add an activity, delete activity, prolong activity) and crossover (mix two plans in a random way).