Algorithms to use for an assignment problem

Here is my problem:

• There are five sewing lines.
• When sample orders arrive, we have to assign them to the available line which is more skilled on a particular garment.
• Each line is given a rank according to their skill level on styles.
• Line capacity should not be exceeded when assigning.
• Also, orders should be sent by the due date.

What is the suitable optimization algorithm to apply for assigning sample orders to sewing lines?
If we use the transportation algorithm, what to do with dummy lines or dummy styles in real-world scenarios?

• Welcome to OR.SE! I suggest you provide more details for your question and explain what is the problem.
– EhsanK
Commented Nov 24, 2023 at 17:04
• EhsanK I updated the description Commented Nov 24, 2023 at 17:50
• Do you know in advance when orders will arrive, or do you update the solution whenever a new order arrives (what is known as an "online" planning problem)?
– prubin
Commented Nov 24, 2023 at 18:30
• @prubin I need plan at the beginning of the week Commented Nov 24, 2023 at 19:29
• Are both line capacity and due date "hard" constraints (must be satisfied, no exceptions) and, if so, how do you handle an order that cannot be assigned in time to meet its due date without violating line capacity?
– prubin
Commented Nov 24, 2023 at 20:45

You can approach this problem using either a mixed-integer linear program (MILP) or a constraint programming (CP) model (using a CP solver that supports global constraints designed for scheduling problems).

For the MILP approach, you can start with binary variable $$x_{o,\ell,d}$$ for each combination of order, line and start date, where $$x_{o,\ell,d} = 1$$ if order $$o$$ is assigned to line $$\ell$$ starting on date $$d$$ and zero otherwise. You will also have a binary variable $$y_o$$ for each order, where $$y_o=1$$ if order $$o$$ is never scheduled. The constraint $$\sum_{\ell, d}x_{o,\ell,d} + y_o = 1\quad\forall o$$ says that every order is either assigned to exactly one line at exactly one starting time or else is skipped.

Your objective function will blend maximizing the skill level of the line (if any) to which each order is assigned and penalizing skipping the order. The due dates are enforced by setting $$x_{o,\ell,d}=0$$ if starting order $$o$$ on line $$\ell$$ on date $$d$$ would result in the due date being missed.

That leaves you with the task of enforcing the capacity limits on the lines. There are multiple ways to do that. You can search this site for questions containing the terms "schedule" (or "scheduling") and "overlap" to find possibilities.

• Is there any implementation of these algorithms using programming languages Commented Nov 30, 2023 at 16:19

Say you've a set of sewing lines $$L = \{l_1,l_2,...l_5 \}$$.
At the beginning of the week you have a set of orders $$O$$, a set of styles $$S$$ & for each style $$s$$ a set of lines in descending order of the rank in skill for that style, for e.g. $$Z^s = \{l_5,l_4,l_3,l_2,l_1 \} \ \ \forall s \in S$$
Assuming each order has a unique style $$O_s$$ & is assigned to a line & remains assigned till completion.
Also assuming orders are completed by a line sequentially i.e. if an order of 2 day duration arrives with sufficient number of days left & a line available it is assumed to be completed on time, else it will not be.

Constraints
$$\sum_o x_{o,l} \le C_ly_l \ \ \forall l \in L$$: C is line capacity with assignment binary var $$x$$

$$y_l \le C_l - \sum_o x_{o,l} \le C_ly_l$$: if some capacity is left then line $$l$$ is open as per binary $$y$$

$$0 \le \sum_l x_{o,l} \le \sum_l y_l \quad \forall o \in O$$: this indicates if an order is assigned to available line or not

If you've duration & due date(or day) of each order defined $$T_o$$ & $$D_o$$ then using $$d$$ start day as another dimension for assignment var $$x$$, you can use\

$$\lambda_o \le (T_o+d)\sum_lx_{o,l,d} - D_o \le D_o\lambda_o \quad \forall d \ \forall o$$: where binary $$\lambda$$ can serve as indicator of delayed order.

Now to assign the available line with max skill for a style $$s$$

$$j = Z_{l}^s$$: get the index of line $$l$$ from set $$Z^s$$: this isn't a constraint, just an assignment

$$y_{l} \le x_{o,l} + (j-1)(\sum_{k=1}^{j-1} x_{o,k})$$

$$\sum_{k=1}^{j-1} x_{o,k} + x_{o,l} \le 1 \ \ \forall l \in Z^s \ \ \forall o$$ where $$s = O_s$$
In the above constraints you are iterating through each of the lines $$l$$ from the ordered set $$Z_s$$ & determining the first available line.
There are other ways to determine the max of the rank but this may be the simplest-already using an ordered set in terms of order of computation