---

Text in pdf-file msp.pdf

Let S, I, and U be the sets of products, tasks, and units respectively. It is assumed that each task produces one product and requires one unit. Define the following input data:

• D_s > 0 is the demand for product s ∈ S;
• s_i ∈ S is the product produced by task i ∈ I;
• u_i ∈ U is the unit suitable for task i ∈ I;
• r_i > 0 is the production rate of task i ∈ I, i.e. the amount of product s_i produced in one hour;
• a_ij is the duration of the changeover task if unit u is switched from task i to task j (assuming that u = u_i=u_j);
• a_i⁰ is the duration of the initial changeover task if task i is performed at the first place on unit u_i;
• T_i^min and T_i^max are the lower and upper time limits for one execution of task i.

The problem asks to choose the set of tasks to be performed and to schedule them so that all the demands are fulfilled, and T_i^min and T_i^max time limits are satisfied. As a primary optimization criterion we chose the minimization of the completion time of the last task (Makespan) denoted by C^max. Two secondary criteria are considered: the minimization of the total changeover time and the total processing time on all units. These criteria are added to the objective function with penalty coefficients P₁ and P₂ that are tunable parameters. The problem is NP-hard [3].

Define the set of positions for each unit u as follows: K_u:={1,2, ... , |I_u|}. Introduce the variables:

• x_ik ∈ {0,1} such that x_ik=1 if and only if task i is assigned to unit u_i at position k ∈ K_u.
• δ_i ≥ 0 is the duration of task i;
• α_uk ≥ 0 is the duration of a changeover task on unit u between positions k and (k+1);
• α_u⁰ ≥ 0 is the duration of an initial changeover on unit u.

The MILP model is as follows:

Subject to

Objective function (1) reflects the primary and the secondary criteria. The allocation constraints (2) - (3) state that each position contains at most one task, and one task is located in at most one position; (4) ensures continuous usage of positions, i.e. if some position is occupied on some unit, then the previous position is occupied as well (this property is useful for modeling the changeover times). Inequalities (5) estimate the produced amount of each product and ensure demands satisfaction.

In (6), the changeover time on unit u between positions k-1 and k is estimated (here M is a large enough parameter that can be defined as M = max_i,j a_ij). One can see that the right hand side value equals a_ij if and only if x_i,k-1 = 1 and x_jk=1, which assures to reserve at least a_ij time units for the changeover if tasks i and j are placed consequently in an actual schedule. In (7), the initial changeover times are estimated.

Inequalities (8) estimate the total processing and changeover time for each unit and bound it by C_max to be minimized. Inequalities (9) bound the processing time of task i to fit in [T_i^min, T_i^max] if task i is performed, or set δ_i=0 otherwise.

REFERENCES

[1] Borisovsky P.A. 2008. "A Genetic Algorithm for One Production Scheduling Problem with Setup Times" In: Applications of optimization methods: Proc. of XIV Baikal International School-seminar Optimization methods and their applications, Vol. 4. Melentiev Energy Systems Institute SB RAS, Irkutsk, Russia. pp. 166-172. (In Russian).

[2] Borisovsky, P.A., Eremeev, A.V., and Kallrath, J. 2017. "On Hybrid Method for Medium-Term Multi-Product Continuous Plant Scheduling." 2017 International Multi-Conference on Engineering, Computer and Information Sciences (SIBIRCON). Novosibirsk. Russia. 18-22 Sept. 2017. IEEE. pp. 42-47.

[3] Dolgui, A., Eremeev, A.V., Kovalyov, M.Y., and Kuznetsov, P.M. 2010. "Multi-Product Lot Sizing and Scheduling on Unrelated Parallel Machines." IIE Transactions 42(7): 514-524.

[4] Eremeev, A.V., Kovalyov, M.Y., and Kuznetsov, P.M. 2018. "Lot-size scheduling of a single product on unrelated parallel machines." Optimization Letters https://doi.org/10.1007/s11590-018-1307-1