.
Valencia Lozano, Fedossova / INGE CUC, vol. 16 no. 2, pp. 131–140. Julio - Diciembre, 2020
Earliness/Tardiness Production Problem using Semi-Infinite Optimization
Problema de Producción temprana/tardía usando Optimización Semi-infinita
DOI: http://doi.org/10.17981/ingecuc.16.2.2020.09
Scientific Research Article. Date Received: 26/07/2019. Acceptance Date: 25/08/2020.
Juan Camilo Valencia Lozano 
Universidad Nacional de Colombia. Bogotá, D.C. (Colombia)
jcvalencias@unal.edu.co
Alina Fedossova
Universidad Nacional de Colombia. Bogotá, D.C. (Colombia)
afedosova@unal.edu.co
Para citar este artículo:
J. Valencia Lozano, A. Fedossova, “Earliness/Tardiness Production Problem using Semi-Infinite Optimization”, INGE CUC, vol. 16, no. 2, pp. 131–140, 2020. DOI: http://doi.org/10.17981/ingecuc.16.2.2020.09
Abstract
Introduction— An Earliness/Tardiness Production Problem is considered, with the objective of delivering products of a company in an optimum time. Based on the problem settled in [1], which was solved with a genetic method, we develop this semi-infinite optimization problem (SIP) with the stochastic outer approximations method created by [2].
Objective— Obtain a better solution of the problem or at least get a similar solution is the goal of this work.
Methodology— With regard to the numerical solution a stochastic outer approximation algorithm was used, in addition numerical experiments were performed in MATLAB.
Results— By last, the algorithm developed will be applied in a real case of Colombian production Company, to give the optimum setting for production planning.
Conclusions— The solution obtained in this work has a bigger function value in contrast with the solutions obtained in [1], [3], but it satisfies all constrains.
Keywords— Earliness/Tardiness production; semi-infinite optimization; outer approximations methods; just-in-time; stochastic algorithms
Resumen
Introducción— Se considera el problema de producción temprana/tardía con el objetivo de distribuir los productos a los clientes en los tiempos óptimos. Basado en el problema descrito en [1], que fue resuelto por ellos con los algoritmos genéticos, el problema se presenta como uno de programación semi-infinita (SIP).
Objetivo— Obtener la mejor solución del problema de la producción temprana/tardía o como mínimo una similar a esta.
Metodología— El método estocástico de aproximaciones externas fue aplicado para obtener solución numérica del problema y los algoritmos fueron programados en MATLAB.
Resultados— Algoritmo propuesto se aplica para un caso real de producción en Colombia y brinda la solución óptima de la planeación de producción.
Conclusiones— La solución obtenida en este trabajo da el valor de la función objetivo ligeramente mayor en comparación con las soluciones obtenidas en [1] y [3], pero cumple todas las restricciones.
Palabras clave— Producción temprana/tardía; optimización semi-infinita; métodos de aproximaciones externas; justo-a-tiempo; algoritmos estocásticos
In this article we are going to show one way to find a solution of a Semi-Infinite Optimization Problem (SIP), which is based on inventory management method called Just-in-Time (JIT). The Just-in-time production is a manufacturing process that prioritize arrival’s time of materials, goods, and labor that are scheduled in the production process. JIT aligns raw-material orders from suppliers directly with production schedules, so that, materials are bought exactly in the time and amount needed, this reduces costs by minimizing warehouse needs. JIT was developed in Japan between 1960 and 1970, particularly at Toyota’s company [4]-[6].
In a JIT system we seek the reduction of the in-process inventory level every second of production labor, which means an infinite number of limitations, that encourage us to introduce the concept of semi-infinite optimization problem [3]. A SIP is an optimization problem with a finite number of variables and an infinite number of constraints [3], [7]. A typical problem with a continua number of constraints is the semi-infinite programming problem (1):
Where f and g are assumed to be continuously differentiable on a neighborhood of X0 × T0, X0 × ℝk and T0 ⊂ ℝk are convex and compact and ℝk is the k-dimensional real space.
Let us consider a company that should produce orders in a specific time interval [0, T]. This example was taken from [1]. For each order i with 1 ≤ i ≤ n and time t ∈ [0, T], define: the decision variable xi, the production cycle Li, the due date di, the function of required resources Ri(t, xi) (3), the function that measures the amount of accessible resources G(t) and we give to each order a weight αi, which is set by its price.
Then we should solve the below SIP (2):
Note that the problem (2) has n variables and the fact that belongs to [0, T] guarantees the existence of infinite constrains.
In order to simplify the problem, we will assume that required resource function behaves as a normal distribution, then it should have the form:
For 1 ≤ i ≤ n. When xi = Li the function (3) should fulfill the condition (4):
With δ a relaxation coefficient between 0 and 1, and Pi the total amount of required resources for the i order. Then if we take δ = 0.97 and for normal distribution properties, we have (5) from [8]:
Also, let us must consider maintenance jobs in the production labor and that they spend some available resources, then suppose that there are maintenance jobs which take place in the time interval previously defined. Every maintenance job requires Qj(t) amount of resource in time t, with 1 ≤ j ≤ m, we used an analog normal distribution to simulate Qj along time. Then we end up with the total able resource function:
And (6) should satisfy
So that our SIP makes sense.
So, we search a vector of optimum time of deliveries, in such a way that the distance between each deliver and the due-date is smaller if those deliveries guarantee that the amount of available resources is bigger than the amount of needed resources.
In the next section we introduce the algorithm that we are going to use to solve the problem.
The stochastic outer approximation method was developed by [2], it is a fixed multi-start method that improves the random search method developed by [9] to solve this type of SIP with continua of constrains.
To use the method, we must define some specific sets. The set (8) of all feasible points linked with the set [0, T] is:
The set of optimal points is (9):
In the same way we can define Xn, t ∈ Tn, where Tn ⊂ [0, T] and Tn is finite subset and X nopt is the subset of optimal points.
Quasi-Optimal Function. Define the function Θ: X0 × Mc ([0, T])→ ℝ (10):
Where X ∈ Mc (X0) and Mc ([0, T]) is the set of all compact subsets of [0, T].
We can check that if x ∈ Xopt implies Θ(x, [0, T]) = 0. We proceed to describe the new algorithm.
SMETH.ETPP illustrate the steps to find an optimal solution of the problem:
It can be seen that SMETH.ETPP is also a Multi-start method. The main difference between this algorithm and the master method is the inclusion of a final step. The master method does not have a proper step where ending of the algorithm was contemplated. We add a restriction to the number of iterations in Step 3 to finish properly the whole program.
Using the stochastic outer approximation method considering a SIP with time as the infinite set of constrains. The same problem described here was solved in [1], with a specially designed genetic algorithm with mutation along the negative gradient direction and in [3] implementing simulated annealing method combined with a heuristic and the steepest descent method.
Utilizing the documentation of MathWorks with some tools from MATLAB Optimization Toolbox, we proceed to resolve the described Earliness/Tardiness production problem, with the proposed algorithm.
The example deals with a construction company which has scheduled orders for different building constructions. The main resource constraint is measuring manpower. The maximum time considered is T = 100 weeks. The available manpower at the beginning of the operation process is g0 = 100 and it increases at a rate of β = 0.005. There are two previously scheduled reparation jobs A and B. For job A, the manpower needed is kilo-hours, it is supposed to be ended at the 40th week and it takes weeks to finish it. For job B, the manpower used is kilo-hours, it is supposed to be finished at the 70th week and it takes 40 weeks to finish it.
The construction cycle, manpower requirement, contract price, and due-date of each order are shown in the next Table 1:
Table 1. Test problem.
|
Constructing |
Resource |
Contract |
Desired |
Completion |
|
|
No. |
cycle |
requirement |
price |
due-date |
time |
|
1 |
20 |
400 |
10 |
25 |
20.00 |
|
2 |
20 |
900 |
18 |
30 |
24.91 |
|
3 |
30 |
800 |
12 |
35 |
78.86 |
|
4 |
40 |
800 |
15 |
40 |
56.91 |
|
5 |
25 |
1000 |
28 |
40 |
39.46 |
|
6 |
20 |
1200 |
20 |
40 |
86.77 |
|
7 |
50 |
2000 |
30 |
50 |
70.74 |
|
8 |
10 |
300 |
18 |
15 |
10.87 |
|
9 |
20 |
400 |
9 |
50 |
76.28 |
|
10 |
60 |
1500 |
30 |
60 |
91.07 |
Source: Authors.
Then, the equations for infinite constraints take the form (11) and (12):
For the resource requirement function in each order, and:
For the resource requirement function in each maintenance job, where Q1 and Q2 are the functions related to the maintenance jobs A and B respectively. And as mentioned in the Problem Description is the total resource required in each job, Wj is the amount of time needed to finish each job and Jj is the specific dates to make the maintenance jobs, then in our example, we have:
D = [200 300],
W = [20 40],
J = [40 70].
Finally define g(xi, t) as in (2). In the following figures Fig. 1 and Fig. 2, the resources function is showed both before and after the optimization method was implemented, respectively.
Fig. 1. Before optimization.
Source: Authors.
Fig. 2. After optimization process.
Source: Authors.
C. Contrasting with Other Methods
After compiling the program times we get the following solutions (Table 2).
Table 2. Results of test problem.
|
Run |
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
x8 |
x9 |
x10 |
fval |
|
1 |
20.0 |
26.3447 |
62.6751 |
47.9448 |
47.5759 |
90.3885 |
88.7749 |
12.1021 |
36.0468 |
90.9367 |
1.3874×105 |
|
2 |
34.3619 |
20.8391 |
38.5331 |
41.3357 |
69.5913 |
48.5448 |
98.1959 |
10.0 |
58.6149 |
10.0 |
1.4735×105 |
|
3 |
20.0 |
24.9111 |
78.8632 |
56.9186 |
39.4681 |
86.7720 |
70.7481 |
10.8756 |
76.2842 |
91.0797 |
1.2027×105 |
|
4 |
20.0 |
33.5344 |
30.0 |
80.4647 |
47.6352 |
88.9213 |
87.7073 |
12.3049 |
52.6507 |
83.1788 |
1.3380×105 |
|
5 |
20.0 |
39.4704 |
88.6194 |
40.0 |
30.5299 |
51.1553 |
91.9886 |
11.6539 |
66.2885 |
98.3180 |
1.4089×105 |
|
6 |
20.0 |
24.5612 |
91.6899 |
76.0440 |
55.1606 |
39.8767 |
91.1598 |
10.5010 |
31.1119 |
94.0920 |
1.5454×105 |
|
7 |
20.0 |
41.3153 |
64.1375 |
85.8654 |
52.1792 |
30.4859 |
93.4855 |
11.4980 |
20.0 |
95.5472 |
1.5322×105 |
|
8 |
20.8032 |
37.5206 |
30.0 |
40.0 |
65.8604 |
49.3244 |
95.2214 |
10.7018 |
77.8988 |
97.7424 |
1.3338×105 |
|
9 |
20.0 |
31.6034 |
30.0 |
86.7238 |
60.3743 |
42.9003 |
95.1213 |
12.1698 |
51.5021 |
99.0656 |
1.5216×105 |
|
10 |
20.0 |
31.5877 |
88.3384 |
40.0 |
61.9669 |
45.3155 |
92.5767 |
10.0 |
20.0921 |
96.4595 |
1.5127×105 |
Source: Authors.
Here we can observe that solution in the 3th run correspond to the minimal value of the function f. This solution shows us the best time in which each order must be delivered. In our example this means, the time to finish each construction order. If we denote our solution as xEG the objective function takes the value:
f(xET) = 1.2027 × 105.
In [1] their optimization process reaches the next solution of the SIP:
xg = [30.74 20.76 41.88 40.79 52.50 86.77 84.38 10.00 75.75 87.28]
And the function takes the value:
f(xg) = 1.1477 × 105
Which means that f(xg) < f(xET) but the solution xg has active constrains in the interval (73, 76.3), then g(xg, t) > 0 for t ∈ (73, 76.3) this fact implies that is not an optimum solution for the problem.
In [3] their optimization process reach the next solution of the SIP:
xg = [31.41 20.56 40.01 40.86 55.60 10.03 43.77 83.30].
The function takes the value:
f(xs) = 1.1296 × 105
which means that f(xs) < f(xET) but the solution xs has active constrains in the intervals (5.7,8.5) ∪ (11,16.2) ∪ (17,24.7) ∪ (39.7,49.7) ∪ (73.9,76.3), then (xg, t) > 0 this fact implies that is not a optimum solution for the problem.
We take data from a Colombian Company that produces refrigerator parts. We applied the outer stochastic approximation method in this Company to optimize the number of workers assigned to different products. The interval of time considered is one month of production. This refrigerator manufacturer has monotonous assembly operations. Just-in-time production planning is ideal for factories which their process is repetitive and systematic [4], because of that we proceed to apply JIT production method in this company.
The data that we will consider is based on 16 products elaborated in the factory, in each one the cycle time it takes to be finished was measured. Data set obtained after measuring is the following (Table 3):
Table 3. Data of real case.
|
Code |
Cycle (Hrs.) |
Resources (Pers.) |
Due-date (Hrs.) |
Price (Cop) |
(Hrs.) |
|
30842092 |
51.72 |
60 |
72 |
22’503.600 |
156.18 |
|
30842101 |
81.66 |
60 |
120 |
38’301.900 |
151.51 |
|
30842102 |
124.66 |
60 |
144 |
53’120.100 |
200.04 |
|
30842104 |
141.66 |
60 |
168 |
64’420.000 |
201.72 |
|
30864015 |
74.5 |
160 |
360 |
19’999.080 |
465.59 |
|
30864030 |
77.17 |
160 |
96 |
22’362.480 |
124.84 |
|
30515111 |
25.27 |
80 |
360 |
8’224.000 |
302.87 |
|
30515112 |
80 |
80 |
120 |
28’632.000 |
98.84 |
|
30515110 |
2.13 |
40 |
240 |
512.900 |
721.13 |
|
30515103 |
1.63 |
40 |
120 |
1’852.600 |
721.13 |
|
30515104 |
1.63 |
40 |
120 |
1’065.600 |
721.13 |
|
30515102 |
1.63 |
40 |
240 |
1’385.900 |
721.13 |
|
30530107 |
516.81 |
80 |
696 |
184’817.598 |
517.68 |
|
30530106 |
209.72 |
80 |
360 |
80’156.840 |
335.59 |
|
30505096 |
353.16 |
80 |
480 |
129’165.300 |
354.04 |
|
30505122 |
23.80 |
110 |
480 |
101’584.600 |
312.72 |
Where Cycle means the time that takes in hours to produce each product. The resources column is the number of people required in each product. Due-date is measured in hours. The price is measured in Colombian pesos. We assumed a rate of resource’s increasing of 0.001. As in the test example, for solving the SIP with JIT model, we will prioritize the different orders by their sell-value. We assume the same objective function and same required resource function as in test example.
Before applying the stochastic outer approximation method to solve the set SIP in this Company, we observe the below graphic of the resource’s function among time (Fig. 3):
Fig. 3. Resource’s function before optimization.
Source: Authors.
The Fig. 3 is a non-convex function and the pick showed around 100 hours means that the company need a big number of workers in that specific time, which implies that more resources are used in that time and there is a sudden increase in production costs. What we try to fix is that necessity, searching a better time for the company to deliver their products and maintain the cost of elaborate new artifacts steady among time.
Fig. 4. Resource’s function after optimization.
Source: Authors.
Fig. 4 represents the same resource’s function after applying the stochastic outer approximation method. With this final solution we can guarantee that the amount of needed resources will be always less or equal to the amount of available resources. To accomplish this objective function is important for the company to have a short number of suppliers and guarantee that each of them shift the materials or resources required in exact time.
To solve the SIP using SMETH.ETPP, we made some assumptions. For the required resource function, we used a function of normal distribution and a relaxation coefficient equal to 1 (13):
These types of functions are not likely to appear in real world factories. Other assumption made in the model is that there is a function that measures the amount of available resources in the company, and such function has an exponential form and without maintenance jobs pre-scheduled (14):
These assumptions made the SIP easier to develop and solve.
As we can see in Fig. 3 there was a high pick in the resource function before implementing the optimization method, so the code used for this problem needed to be changed in the dropping of active constrains, because dropping constrains near to the pick, will ignore a large number of active constrains and will end up with a bad solution of the minimization problem. It was necessary to drop fewer active constrains and change the tolerance parameter while clustering, this change affected the number and duration of program’s iterations compared to the iterations made in test problem.
Project name: Optimización de producción temprana/tardanza mediante programación semi-infinita. Code: 38696. Universidad Nacional de Colombia. Sede Bogotá. Date: 24-08-2017 / 27-07-2019.
The solution obtained in this work has a bigger function value in contrast with the solutions obtained in [1] and [3] but it satisfies all constrains.
It is necessary to develop a faster way to drop active constrains in cases where the function of constrains has picks or is not convex.
Just-in-time management plan is well posed on a company like the used in the real case because setting a steady number of orders is easy and suppliers will know the amount of resources required in advance.
While implementing the stochastic outer approximation method in a test example is quite direct and natural, applying the same method in a real-world problem becomes much harder. In real life is almost impossible to find smooth functions that tell us the number of available and required resources along time.
[1] D. Wang & S.C. Fang, “A semi-infinite programming model for earliness/tardiness production planning with a genetic algorithm,” Computers Math Applic, vol. 31, no. 8, pp. 95–106, Apr. 1996. https://doi.org/10.1016/0898-1221(96)00034-X
[2] Y. Volkov & S.K. Zavriev, “A general stochastic outer approximations method,” SIAM J Control Optim, vol. 35, no. 4, pp. 1387–1421, 1997. https://doi.org/10.1137/ S0363012994263202
[3] D. Wang & Y. Li, “A semi-infinite programming model for earliness/tardiness production planning with simulated annealing,” Math Comput. Modelling, vol. 26, no. 7, pp. 35–42, Oct. 1997. https://doi.org/10.1016/S0895-7177(97)00184-2
[4] R.Z. Ríos & Y.A. Ríos, Just-in-time systems. NY, USA: Springer, 2012.
[5] JMA, Kanban and JUST-IN-TIME in TOYOTA. BR, USA: Routledge, 2017. https://doi.org/10.1201/9780203749722
[6] T. Molina Salazar, “Impacto de las Técnicas de Producción y las Prácticas de Calidad en los Beneficios JIT,” Cultura Científica y Tecnológica, vol. 14, no. 63, pp. 88–101, 2017.Available: http://erevistas.uacj.mx/ojs/index.php/culcyt/issue/viewIssue/605/716
[7] S.Y. Gao, J. Sun, J. & S. Wu, “A semi-infinite programming approach to two-stage stochastic linear programs with high-order moment constraints,” Optim Lett, vol. 12, no. 6, pp. 1237–1247, Aug. 2018.https://doi.org/10.1007/s11590-016-1095-4
[8] G. Blom,.Probability and Statistics Theory and Applications, NY, USA: Springer, 1989.
[9] Y. Wardi, “A Stochastic Algorithm for Optimization Problems with Continua of Inequalities,” J Optim Theory Appl, vol. 56, no. 2, pp. 286–311, Feb. 1998. https://doi.org/10.1007/BF00939413
Juan Camilo Valencia Lozano is Mathematics Professional from Universidad Nacional de Colombia (Bogotá, D.C.). https://orcid.org/0000-0001-7925-5644
Alina Fedossova is Professional in Applied Mathematics (Universidad Estatal de Moscú – Lomonosov). Ph.D. in mathematical - Physical (Universidad Estatal de Moscú – Lomonosov). Full Time Professor UNAB (Bucaramanga, Colombia) 1995-1997, 2000-2006. Exclusive Professor Universidad Nacional de Colombia (Bogotá, D.C.) since 2007. https://orcid.org/ 0000-0003-4944-633X