In this paper, a new problem of job sequences in a workshop is presented, taking into account non-unit demands for the jobs and whose objective is to minimize the total completion time for all the jobs (\({C}_{max}\)) satisfying a set of restrictions imposed on the problem to preserve the production mix. Two procedures are proposed to solve the new problem: Mixed Integer Linear Programming and a Metaheuristic based on Multistart and Local Search. The two proposed procedures are tested using instance set Nissan-9Eng.I, in both cases giving rise to highly satisfactory performance both in quality of solutions obtained and in the CPU times required. Through a case study of the Nissan engine manufacturing plant in Barcelona, our economic-productive analysis reveals that it is possible to save an average of € 1162.83 per day, manufacturing 270 engines, when we transform the current assembly line into a Heijunka-Flow Shop.
Hinweise
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Preliminaries
The Flow Shop Scheduling Problem (FSP) is a sequencing problem that has received considerable attention from professionals and researchers in recent decades due in part to the wide range of production environments it can model [19].
A recent version of FSP is the \(Fm\)/\(\beta\)/\(\gamma\)/\(d_{i}\) family of sequencing problems [3] and 2020), which is to establish an application between the elements of a set \({\text{{T}}}\) of ordinals (\(T\) elements) corresponding to the positions in the production sequence: \(\pi \left( {T) = (\pi _{1} ,.,\pi _{T} } \right)\), and the elements of a set \(J\) of jobs or products (\(D\) elements, with \(D = T\)).
Anzeige
The jobs or products in group \(J\) are classified into exclusive types or classes, \(J_{i}\), satisfying the following properties: \(J = \bigcup\nolimits_{{i \in I}} {J_{i} }\) and \(J_{i} \cap J_{{i^{\prime}}} = \emptyset ,{\text{~}}\forall \left\{ {i,i^{\prime}} \right\} \in I\), where \(I\) is the set of job types \(\left( {i = 1,..,n} \right)\).
In \(Fm\)/\(\beta\)/\(\gamma\)/\(d_{i}\) problems, the \(\beta\) parameter can take the permutation (prmu) or blocking (block) values, while the \(\gamma\) parameter corresponds the efficiency metrics to optimize \((C_{{max}} ,~C_{{med}}\), etc.), vector \(\vec{d} = \left( {d_{1} ,d_{{2,}} ..,d_{n} } \right)\) represents the demand plan for the considered job types, and \(d_{i}\) symbolizes the number of jobs of type \(i \in I\) within \(J\), that is to say \(d_{i} = \left| {J_{i} } \right|~\forall i \in I\), satisfying: \(\mathop \sum \nolimits_{{\forall i}} d_{i} = D = T.\)
The units of \(J\) travel in order through a set \(K\) of \(m\) stations on an assembly line arranged in series, and the production of a job of type \(i \in I\) requires a heterogeneous processing time \(~p_{{i,k}}\) in workstation \(k \in K\)\(\left( {k = 1,..,m} \right)\).
The purpose of problems \(Fm\)/\(\beta\)/\(\gamma\)/\(d_{i}\) is to obtain a sequence of replicated jobs or products (\(d_{i}\)), in a line with \(m\) machines, with the possibility of blocking or not, according to the \(\beta\) parameter, and with the objective of optimizing the efficiency metric represented by the \(\gamma\) parameter \((C_{{{\text{max}}}} ,~C_{{{\text{med}}}} ,{\text{etc}}.)\).
Anzeige
Therefore, using the notation proposed by Graham et al. [11], both the \(Fm\)/\(prmu\)/\(\gamma\) problems [1, 10, 13, 20, 22, 23] as the \(Fm\)/\(block\)/\(\gamma\) problems [4, 8, 16, 18, 21] are particular cases of the family \(Fm\)/\(\beta\)/\(\gamma\)/\(d_{i}\), when \(d_{i} = 1\) for all \(i \in I\).
On the other hand, completing all jobs in the shortest time possible \(\left( {\min C_{{{\text{max}}}} } \right)\)) is not the only desirable objective when establishing a product manufacturing sequence. In production environments that are governed by the Just-in-Time manufacturing ideals [17], the production sequences must have properties that are linked to the Heijunka concept [9, 12, 14], whose meaning is to achieve regularity of production.
El The Heijunka (regularity) concept can be applied to any constituent element of Just in Time production, the most obvious criteria being the following:
C1.
Regularize the consumption of the parts. The purpose of this criterion is to control the stock levels of the component parts of mixed products (e.g., in the manufacture of engines: block, cylinder head, cylinders and pistons, camshaft, gear change, etc.) throughout the manufacturing process on the assembly line.
C2.
Regularize workloads at line stations. The purpose of this criterion is to avoid or smooth the work overloads that are generated when a manufacturing sequence consecutively contains a series of products rich in process time. This criterion is purely ergonomic and its objective is to avoid or reduce the risk of injury to line operators due to intermittent overloads.
C3.
Regularize the manufacture of mixed products throughout the manufacturing sequence. This criterion tries to collect, in a simple way and to facilitate management, the benefits of criteria C1 and C2, since it encourages, without optimizing, both the regularity of the consumption of the component parts and the regularity of the workloads in the production line.
On the other hand, the incorporation of Heijunka in production sequence problems can be characterized by three methods:
M1.
Constraints: For example, imposing minimum and maximum manufacturing levels on the job types \(\left(i=1,...,n\right)\) in each manufacturing cycle \(\left(t=1,\dots ,T\right)\) and/or imposing minimum and maximum consumption values on the component parts of mixed products in each manufacturing cycle.
M2.
Objective function: Maximizing the constancy of the product manufacturing rates [15] and/or the component consumption rates [5] and/or the rates of the required processing times in the workstations.
M3.
Mixed characterization: There is also the possibility of establishing a mixed characterization of Heijunka, which incorporates into the sequence models the two previous methods: (a) restrictions and (b) an objective function.
In this work, the third criterion (C3) and the first method (M1) have been added to the genuine \(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem to achieve sequences with minimum makespan (\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\): time that elapses from the start of work to the end) and with some properties that propitiate the regularity of product manufacturing through restrictions.
The main contributions of this work are: (i) description and formulation of a new problem that we call \(Hejunka-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\); (ii) design and implementation of a Metaheuristic based on Multistart and Local Search (MS-Q) to solve the new problem; (iii) a computational analysis of MS-Q and MILP (CPLEX solver) performance in CPU time and quality of solutions using real-dimension instances related to case study; and (iv) an economic-productive feasibility study to implement the solutions on a production line.
The remaining text has the following structure. Section 2 is dedicated to presenting the new problem under study which is illustrated with an example in Sect. 3. In Sect. 4, the designed MS-Q procedure is described. In Sect. 5, a case study with its data is shown, as well as the procedures used and their results. Finally, Sect. 6 offers some conclusions about this work.
2 \({\text{Heijunka}} - Fm\)/\(prmu\)/\(\user2{C}_{{{\text{max}}}}\)/\(\user2{d}_{\user2{i}}\) Problem
To incorporate Heijunka, we will indicate that the sequence \(\pi \left(T\right)=\left({\pi }_{1},\dots ,{\pi }_{T}\right)\), which is composed of \(T\) units of jobs, has the property of preservation of the production mix if the set of restrictions (1) is satisfied. We also call this property Quota property:
$$ \lambda _{i} t \le X_{{i,~t}} \le \lambda _{i} t \equiv \left| {X_{{i,~t}} - \lambda _{i} t} \right| < 1~~\forall i \in I,\;~\forall t \in {\rm T};\,X_{{i,~T}} = d_{i} \;\forall i \in I $$
(1)
where:
\(I:\) set of product types, \(i = 1,..,\left| I \right|\).
\({\text{{\rm T}}}\): set of manufacturing cycles in every demand plan, \(t = 1,..,\left| {\text{{\rm T}}} \right|\); \(T \equiv \left| {\text{{\rm T}}} \right|\).
\(d_{i} :\) demand for units of type \(i \in I\) in an arbitrary demand plan.
\(\lambda _{i} :\) proportion of units of type \(i \in I\): \(\lambda _{i} = d_{i} /T\)\(\forall i \in I\).
\(X_{{i,{\text{~}}t}} :\) number of units of type \(i \in I\) in the partial sequence \(\pi \left( t \right) \subseteq \pi \left( T \right)\): actual production associated with the partial sequence \(\pi \left( t \right)\).
The Quota property (1) imposes that the actual production \(X_{{i,~t}}\), for every product (\(i \in I\) and every manufacturing cycle \(t \in {\text{{\rm T}}}\), must be an integer as close as possible to its ideal production \(\lambda _{i} t\). The ideal production (\(\lambda _{i} t\)) is defined as the quota of manufacturing time given to a product (\(i \in I\)) until the end of each production cycle (\(t = 1,..,\left| {\text{{\rm T}}} \right|\)).
Under such conditions, we can present a model for the \(Fm\)/\(prmu\)/\(C_{{{\text{max}}}}\)/\(d_{i}\) that accounts for two types of aspects:
Efficiency: objective function to minimize the maskespan \(C_{\text{max}}\).
Technical-productive: Quota property to enforce preservation of the production mix in the Heijunka manufacturing sequence \(\pi \left( T \right).\)
Effectively, assuming the following data is known:
The set of job types \(\left( {I:i = 1,..,\left| I \right|} \right)\) and the set of stations \(\left( {K:k = 1,..,\left| K \right|} \right)\).
The processing times \(p_{{i,k}} ~\left( {i \in I{ \curlywedge }k \in K} \right)\) of the operations.
The demand vectors \(\vec{d} = \left( {d_{1} , \ldots ,d_{{\left| I \right|}} } \right)\) and production mix \(\vec{\lambda } = \left( {\lambda _{1} , \ldots ,\lambda _{{\left| I \right|}} } \right)\).
The problem is finding a Quota sequence of \(T\) jobs \(\pi \left( T \right) = \left( {\pi _{1} , \ldots ,\pi _{T} } \right)\) with minimum makespan \(C_{{{\text{max}}}}\) that satisfies the demand plan represented by the vector \(\vec{d}\). The formulation of the model is as follows.
$$ X_{{i,~t}} = \left| {\left\{ {\pi _{\tau } \in \pi \left( t \right) \subseteq \pi \left( T \right):~\pi _{\tau } = i \in I} \right\}} \right|~~~\forall i \in I~\forall t = 1,..,T $$
(5)
$$ \lambda _{i} t \le X_{{i,~t}} \le \lambda _{i} t~~\forall i \in I~\forall t = 1,..,T $$
(6)
$$ ~X_{{i,~T}} = d_{i} ~~\forall i \in I~ $$
(7)
$$ C_{{k,0}} = 0\;\forall k \in K $$
(8)
$$ C_{{0,t}} = 0\;\forall t = 1,..,T $$
(9)
In the model Q-FSP, the identity (2) expresses the minimization of the objective function \({\mathcal{F}}\left( {\pi \left( T \right)} \right)\) that attends to the time of completion of the last job or product \(\pi _{T}\) of the production sequence \(\pi \left( T \right)\) in the last machine \(\left( {k = m} \right)\); that is: \(C_{{{\text{max}}}} \equiv C_{{m,T}}\). The equality (3) determines the minimum time of completion of the \(t\)-th job \(\pi _{t}\) in production sequence \(\pi \left( T \right)\) in machine \(~k \in K:~C_{{k,t}} \left( {\pi _{t} } \right).~\) Meanwhile, the equality (4) determines the minimum start time \(S_{{k,t}}\) of the \(t\)-th job \(\pi _{t}\) in \(\pi \left( T \right)\) in machine \(~k \in K.~\) Formula (5) serves to count the number of jobs of type \(i \in I\) in the partial sequence \(\pi \left( t \right) \subseteq \pi \left( T \right)\). The conditions (6) impose the Quota property on the manufacturing sequence \(\pi \left( T \right)\). The equalities (7) impose the satisfaction of the demand plan \((d_{i} ~\forall i \in I)\). Finally, conditions (8) and (9) set the start of completion times.
3 An illustrative example
In order to illustrate the problem under study, the following example is presented: There are 6 jobs or products (\(T = 6\)), of which 3 are type A, 1 is type B, and 2 are type C. The units of product are processed in 3 workstations (\(\left| K \right| = 3\)) with different processing times. The processing time of each unit of type of product (A, B, C) in each workstation \(\left( {m_{1} ,m_{2} ,m_{3} } \right)\) is that set out in Table 1.
Table 1
Processing times (\(p_{{i,k}}\)) required by the units of product, according to type, in each workstation
The total processing time required to the production line is\(p_{{{\text{tot}}}} = 77\)
The optimal manufacturing sequence for the proposed example, in order to minimize the completion time of all the jobs on the production line \(\left( {C_{{{\text{max}}}} } \right)\), for the problem \(Fm\)/\(prmu\)/\(C_{{{\text{max}}}}\)/\(d_{i}\) is \(\pi _{1} \left( 6 \right) = \left( {C,C,A,A,A,B} \right)\). Figure 1 shows the Gantt chart for this sequence.
Fig. 1
Gantt chart for the sequence \({\pi }_{1}\left(6\right)=(C,C,A,A,A,B)\). The sequence \({\pi }_{1}\left(6\right)\) is optimal for the problem \(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\), and its value is \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}({\pi }_{1})=33\)
×
For its part, Fig. 2 shows the Gantt chart corresponding to an optimal sequence for the problem \({\text{Hejunka}} - Fm\)/\(prmu\)/\(C_{{{\text{max}}}}\)/\(d_{i}\), in which the satisfaction of the Quota property of all types of product is imposed in all manufacturing cycles. The sequence \(\pi _{2} \left( 6 \right) = \left( {C,A,A,C,A,B} \right)\) has a value of the objective function \(C_{{{\text{max}}}} \left( {\pi _{2} } \right) = 34\).
Fig. 2
Gantt chart for the sequence \({\pi }_{2}\left(6\right)=(C,A,A,C,A,B)\). The sequence \({\pi }_{2}\left(6\right)\) is optimal for the \(Hejunka-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem, and its value is \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}({\pi }_{2})=34\)
×
Considering the sequences \(\pi _{1} \left( 6 \right)\) y \(\pi _{2} \left( 6 \right)\), it can be stated:
(i)
The solution \(\pi _{1} \left( 6 \right)\) presents a value of \(C_{{{\text{max}}}}\) less by one unit of time than that corresponding to the solution \(\pi _{2} \left( 6 \right)\)\(({\text{i}}.{\text{e}}.:C_{{{\text{max}}}} \left( {\pi _{2} } \right) - C_{{{\text{max}}}} \left( {\pi _{1} } \right) = 34 - 33 = 1)\). This means that \(\pi _{1} \left( 6 \right)\) is more efficient than \(\pi _{2} \left( 6 \right)\) in terms of completion time for all jobs.
(ii)
The solution \(\pi _{2} \left( 6 \right) = \left( {C,A,A,C,A,B} \right)\) satisfies the Quota property at all positions in the sequence.
(iii)
The solution \(\pi _{1} \left( 6 \right) = \left( {C,C,A,A,A,B} \right)\) violates the Quota property at 3 positions in the sequence, as detailed in Table 2.
Table 2
Solution \(\pi _{1} \left( 6 \right) = \left( {C,C,A,A,A,B} \right)\): the values of the accumulated productions \(X_{{i,~t}}\) and the intervals \(\left[ {a,b} \right]\) are shown
\(i\)
\(t = 1\)
\(t = 2\)
\(t = 3\)
\(t = 4\)
\(t = 5\)
\(t = 6\)
\(X_{{i,~t}}\)
\(\left[ {a,b} \right]\)
\(X_{{i,~t}}\)
\(\left[ {a,b} \right]\)
\(X_{{i,~t}}\)
\(X_{{i,~t}}\)
\(X_{{i,~t}}\)
\(\left[ {a,b} \right]\)
\(X_{{i,~t}}\)
\(\left[ {a,b} \right]\)
\(X_{{i,~t}}\)
\(\left[ {a,b} \right]\)
A
0
[0,1]
0
[1,1]
1
[1,2]
2
[2,2]
3
[2,3]
3
[3,3]
B
0
[0,1]
0
[0,1]
0
[0,1]
0
[0,1]
0
[0,1]
1
[0,1]
C
1
[0,1]
2
[0,1]
2
[1,1]
2
[1,2]
2
[1,2]
2
[2,2]
The values \(a = \lambda _{i} t\) and \(b = \lambda _{i} t\) are respectively lower and upper limits that are imposed on the variables \(X_{{i,~t~}} \left( {\forall i\forall t} \right)\) to achieve a Quota sequence
In view of Table 2, we can state that the sequence \(\pi _{1} \left( 6 \right) = \left( {C,C,A,A,A,B} \right)\) does not satisfy the Quota property for product types A and C in the cycle \(t = 2\) nor for product type C in cycle \(t = 3,{\text{~therefore}},{\text{~the~sequence~}}\pi _{1} \left( 6 \right)\) violates the Quota property in 8.33% of the constraints.
In the subsection dedicated to the implementation of solutions in a production line, the advantages offered by planning sequences satisfying the Quota property within the Heijunka ideology are described.
4 Metaheuristic procedure for \(\user2{Heijunka} - \user2{Fm}\)/\(\user2{prmu}\)/\(\user2{C}_{{\user2{max}}}\)/\(\user2{d}_{\user2{i}}\)
The proposed metaheuristic is based on a Multistart procedure with Local Search similar to Bautista and Alfaro [2]. Indeed, the proposed procedure, MS-Q, consists of a first phase (constructive phase) which provides an initial solution through a randomized greedy procedure, and a second phase (improvement phase) which uses local search procedures to reach the local optima in one or more specific neighborhoods.
After setting a prefixed number of iterations (construction plus improvement), MS-Q metaheuristic obtains in phase-1 manufacturing sequences, \(\pi \left(T\right)=({\pi }_{1},\dots ,{\pi }_{T})\), that satisfy the Quota property, and then, in phase-2, those sequences are subjected to local optimization in order to minimize the completion time of the last job in the last workstation, that is: \(C_{{{\text{max}}}}\).
4.1 Phase 1: construction of a Quota sequence
The problem of the construction of a Quota sequence, which we will call Quota-Product Rate Variation Problem (Q-PRV), can be formulated as a Binary Linear Programming (BLP) representing maximum constraints satisfaction problem, as follows.
$$ X_{{i,~t}} = \mathop \sum \limits_{{\tau = 1}}^{t} x_{{i,~\tau }} ~~~~~~\forall i = 1,..,n;~\forall t = 1,..,T $$
(13)
$$ \left| {X_{{i,~t}} - \lambda _{i} t} \right| < 1 + z_{{i,~t}} ~~~~~\forall i = 1,..,n;~\forall t = 1,..,T $$
(14)
$$ x_{{i,~t}} \in \left\{ {0,1} \right\}~~~~~~\forall i = 1,..,n;~\forall t = 1,..,T $$
(15)
$$ z_{{i,~t}} \in \left\{ {0,1} \right\}~~~~~~\forall i = 1,..,n;~\forall t = 1,..,T $$
(16)
$$ X_{{i,~t}} \in \mathbb{Z}^{ + } \cup \left\{ 0 \right\}~~~~~~\forall i = 1,..,n;~\forall t = 1,..,T $$
(17)
where \(x_{{i,{\text{~}}t}}\) (\(\forall i\forall t)\) is a binary variable that equals 1 if and only if a unit of type of product \(i \in I\) occupies position \(t\) of the manufacturing sequence \(\pi \left( T \right)\), while binary variable \(z_{{i,{\text{~}}t}}\) (\(\forall i\forall t)\) takes the value 0 when the type of product \(i \in I\) satisfies the property Quota in the production cycle \(t\) and is equal to 1 otherwise.
In the Maxsat Q-PRV model, the objective function (10) corresponds to the minimization of the number of Quota constraints violated \(({\mathcal{Z}}_{{{\text{sum}}}} )\). Equalities (11) impose that each position in the sequence has a job assigned, while equalities (12) force compliance with the demand plan \(\vec{d} = \left( {d_{1} , \ldots ,d_{n} } \right)\). The equalities (13) are used to determine the accumulated productions \(X_{{i,{\text{~}}t}}\) (\(\forall i\forall t)\) of all types of jobs and up to each manufacturing cycle. The inequalities (14) force the satisfaction of the Quota property by all types of jobs (\(\forall i \in I\)) in all positions of the sequence (\(\forall t \in {\text{{\rm T}}})\). Finally, conditions (15) and (16) impose that the variables \(x_{{i,{\text{~}}t}}\) and \(z_{{i,{\text{~}}t}}\) are binary, while conditions (17) force the accumulated production (\(X_{{i,{\text{~}}t}} )\) are integers and not negative.
To generate Quota sequences in accordance with the Maxsat Q-PRV model, an enumerative deterministic procedure can be designed based on the branching and cutting of partial solutions; however, in this work we have chosen to use random to promote the diversity of the initial solutions generated in Phase 1, thus allowing them to belong to different regions of the feasible solutions space.
Another indirect way of constructing sequences that satisfy all or a large part of the Quota constraints (14) is to determine integer values for the real production variables \(X_{{i,{\text{~}}t}}\) as close as possible to their ideal values \(\lambda _{i} t\) and that, in addition, these values are consistent with the rest of the restrictions of the Maxsat Q-PRV model. To do this, it is enough to change the objective function (10) for a function that measures the discrepancies between the real and ideal accumulated productions. Some examples of discrepancy functions that we refer to are the following:
In this work, the function (18), sum of quadratic discrepancies: \(~\Delta _{1} \left( {\pi \left( T \right)} \right)\), is fundamental to construct a random generator of Quota sequences.
First, in Phase 1 a sequence of jobs \(\pi \left( T \right) = \left( {\pi _{1} , \ldots ,\pi _{T} } \right)\) is constructed satisfying the Upper Quota property (\(({\text{i}}.{\text{e}}.\;X_{{i,~t}} \le \lambda _{i} t,~\;\forall i\forall t)\)), progressively and assigning at each stage \(t{\text{~}}\left( {t = 1, \ldots ,T} \right){\text{~}}\) a job from the \({\text{CL}}\left( t \right)\) list of candidates that can be drawn to occupy the position \(t\) of the manufacturing sequence. Consequently, when stage \(t\) is reached, it is added to the sequence consolidated in the previous stage, \(\pi \left( {t - 1) = (\pi _{1} ,.,\pi _{{t - 1}} } \right),\) a job \(i \in {\text{CL}}\left( t \right)\). List \(CL\left( t \right)\) is constructed like this:
where \(n_{i}\) is the number of jobs of type \(i \in I\) that contains the production sequence \(\pi \left( {t - 1) = (\pi _{1} ,.,\pi _{{t - 1}} } \right)\).
Therefore, for a job type \(i \in I\) to enter the list \(CL\left( t \right)\) of stage \(t\), it must meet the following two conditions:
1.
The job type does not have its demand fulfilled: \(n_{i} = X_{{i,{\text{~}}t - 1}} < d_{i}\).
2.
The difference between the upper Quota value \(\lambda _{i} t\), corresponding to the ideal production of stage \(t\), and the consolidate production up to the previous stage must be greater than or equal to one unit: \(\lambda _{i} t - n_{i} \ge 1\).
Note that the candidate list, \({\text{CL}}\left( t \right)\), only contains jobs or products that satisfy the upper Quota property; this is done like this because if the strict satisfaction of the Quota property is imposed: \(\lambda _{i} t \le n_{i} + 1 \le \lambda _{i} t \equiv \left| {n_{i} + 1 - \lambda _{i} t} \right| < 1\), then there is a risk, and this is often the case, that \({\text{CL}}\left( t \right)\) remains empty.
Second, the sum of quadratic discrepancies associated with each candidate job that is contained in the list \({\text{CL}}\left( t \right)\) is evaluated, using the indices \(g_{i}^{{\left( t \right)}}\):
$$ g_{i}^{{\left( t \right)}} = \mathop \sum \limits_{{k = 1}}^{n} \left( {n_{k} + \delta _{{i,k}} - \lambda _{k} t} \right)^{2} ~~\forall i \in {\text{CL}}\left( t \right) $$
(23)
where \(n_{k}\) is the number of jobs of type \({\text{~}}k \in I\) that contains the sequence consolidated in the previous stage, \(\pi \left( {t - 1} \right)\), and \(\delta _{{i,k}}\) is the Kronecker delta: \(\delta _{{i,i}} = 1{ \curlywedge }\delta _{{i,k}} = 0\;{\text{~if}}\;~i \ne k\).
Third, the jobs in the list \({\text{CL}}\left( t \right)\) are ordered according to the increasing order of the priority indices \(g_{i}^{{\left( t \right)}}\), giving rise to the ordered list \(\overline{{{\text{CL}}}} \left( t \right)\).
Alternatively, the sorting of the list \({\text{CL}}\left( t \right)\) to construct the list \(\overline{{{\text{CL}}}} \left( t \right)\) can be made more efficient by using the priority indices \(f_{i}^{{\left( t \right)}}\) which are defined as in (24).
$$ f_{i}^{{\left( t \right)}} = \lambda _{i} t - n_{i} ~~\forall i \in {\text{CL}}\left( t \right) $$
(24)
The equivalence between the orderings of the jobs according to the indices \(g_{i}^{{\left( t \right)}}\) and \(- f_{i}^{{\left( t \right)}}\) is demonstrated below.
Theorem 1
Given a partial sequence of jobs \(\pi \left(t-1)=({\pi }_{1},.,{\pi }_{t-1}\right)\) and a list of jobs \(CL\left(t\right)\) constructed according to (22), then, the ordering of jobs of \(\mathrm{C}\mathrm{L}\left(t\right)\) according to the indices \({g}_{i}^{\left(t\right)}\) (see (23)) is opposite to the ordering according to the indices \({f}_{i}^{\left(t\right)}\) (see (24)).
Proof
Indeed, let \({H}_{k,t}={n}_{k}-{\lambda }_{k}t\)\((\forall k\in I,\forall t\in \mathrm{{\rm T}})\), then, it can be stated:
After this ordering, the list \(\overline{{{\text{CL}}}} \left( t \right)~\) is reduced through a mechanism that is a function of the admission factor \(\alpha\) (percentage of candidate jobs), with this operation, the restricted list \(\overline{{{\text{RCL}}}} \left( {t,\alpha } \right)\) is obtained, which coincides with \(\overline{{{\text{CL}}}} \left( t \right)~\) when \(\alpha = 100\% = 1\), while if \(\alpha = 1/\left| I \right|\), the best candidate job from such lists is selected at each stage \(t\).
Taking into account all the above, Algorithm A1 is formalized.
×
Note that Algorithm A1 is a general method of generating Upper Quota sequences, \(\pi \left(T\right)\), independently of any other goal. Sometimes, the Algorithm A1 obtains solutions that also satisfy the Lower Quota property \(\left( {\lambda _{i} t \le X_{{i,{\text{~}}t}} {\text{~~}}\forall i \in I{\text{~}}\forall t \in {\text{{\rm T}}}} \right)\), when this purpose is not achieved then Algorithm A2 is run.
×
The \({\text{MAXSAT}}\) procedure in A2 (Line 19 from A2) is an exchange algorithm, based on Local Search with exhaustive descent, that solves the Maxsat Q-PRV problem satisfying the constraints (14): \((\left| {X_{{i,~t}} - \lambda _{i} t} \right| < 1,{\text{~}}\forall i~\forall t)\), which provides as a solution a sequence \(\hat{\pi }\left( T \right)\) that does satisfy the Quota property in all of the manufacturing cycles.
Specifically, MAXSAT algorithm starts from the solution \(~\pi \left( T \right)\) generated by Algorithm A1 and performs in each iteration the exchange of the jobs of every pair of positions of the current sequence \(\hat{\pi }\left( T \right)\), consolidating, in each iteration, the Last sequence that minimizes the number of Quota constraints violated. The execution of the MAXSAT algorithm ends when \({\mathcal{Z}}_{{{\text{sum}}}} \left( {\hat{\pi }\left( T \right)} \right) = 0\) or \({\mathcal{Z}}_{{{\text{sum}}}}^{{\text{'}}} \left( {\hat{\pi }\left( T \right)} \right) = \left| I \right| \times T\) (see formula (10)).
Obviously, the CPU time efficiency of the MAXSAT procedure is higher the lower the number of Quota constraints violated by the initial sequence \(\pi \left( T \right)\); for this reason, the sequences provided by the A1 algorithm are used, since they comply with the Upper Quota property and tend to comply with the Lower Quota property when the values of the admission factor \(\alpha\) are small.
4.3 Phase 2: improvement \(\user2{C}_{{{\text{max}}}}\) of the quota sequences through local search
The improvement phase starts with a Quota sequence \(\hat{\pi }\left( T \right)\) in which five descent algorithms are run consecutively and repetitively in five neighborhoods (three exchange and two insertion) until none of them improves the best solution that is achieved during the iteration. From two arbitrary Quota sequences, the one that offers the least total completion time \(\left( {C_{{{\text{max}}}} } \right)\) is selected. The descent algorithms are based on the exchange and insertion of jobs, and they are oriented to the exploration of sequence cycles in both increasing and decreasing order. The five descent algorithms are:
LS1.
Forward exchange for ranges of job types: For all \(t\) position of the current sequence, \(\hat{\pi }\left( T \right)\)., the job type is determined that is in that position and the next closest locus is searched, \(t^{'} > t\), that is occupied by the same type (i.e., \(\hat{\pi }_{t} = \hat{\pi }_{{t^{\prime}}}\)); if no such locus exists, then its value is set by making \(t^{'} = T + 1\). Just after, the tentative exchange between \(\hat{\pi }_{t}\) and the jobs located in the range \(\left[ {t + 1,t^{'} - 1} \right]\) of the sequence is made. The first exchange that reduces the total completion time \(C_{{{\text{max}}}} \equiv C_{{m,T}}\) (see (2)) is consolidated as long as the resulting sequence satisfies the Quota property.
LS2.
Backward exchange for ranges of job types: This procedure is similar to the previous one, but in this case the search is performed for \(t = T\) to 1 step -1. Obviously, if the previous closest locus, \(t^{'} (t^{'} < t)\), with the same job type \(\left( {\hat{\pi }_{t} = \hat{\pi }_{{t^{\prime}}} } \right)\) does not exist, it is considered \(t^{'} = 0\). The first exchange that reduces \(C_{{{\text{max}}}}\) is consolidated as long as the resulting sequence satisfies the Quota property.
LS3.
Complete exchange between pairs of positions: This procedure is used to reinforce the previous two and uses a larger neighborhood. At each iteration, for all position \(t\) of the current sequence \(\hat{\pi }\left( T \right)\), the job of the locus\(t\) is exchanged with the job of the locus\(t^{'} \in \left[ {t + 1,T} \right]\), if \(\hat{\pi }_{t} \ne \hat{\pi }_{{t^{\prime}}}\). The last job exchange that minimizes \(C_{{{\text{max}}}} \equiv C_{{m,T}}\) is consolidated, provided the Quota property is satisfied.
LS4.
Forward insertion for ranges of job types: For all \(t\) position of the current sequence, \(\hat{\pi }\left( T \right)\), the job type in the \(t\) position is detected and the next closest locus \(t^{'} (t^{'} > t)\) is searched that is occupied by the same type \((\hat{\pi }_{t} = \hat{\pi }_{{t^{\prime}}} )\); if these locus does not exist, it is considered \(t^{'} = T + 1\). Following, the \(\hat{\pi }_{t}\) job is inserted in the range of sequence positions \(\left[ {t + 1,t^{'} - 1} \right]\). Then, the first insertion that leads to reduce \(C_{{{\text{max}}}} \equiv C_{{m,T}}\) is done as long as the resulting sequence satisfies the Quota property.
LS5.
Backward insertion for ranges of job types: This insertion procedure is similar to LS4 with respect to the neighborhood, and analogous in the search for types of jobs to LS2.
While there is improvement, the above five algorithms are repeated.
5 A case study in an engine plant
5.1 Data set
The computational experience proposed here is focused on comparing the MS-Q and MILP (Mixed Integer Linear Programming) procedures in terms of the quality of the solutions and the CPU times. As in Bautista-Valhondo and Alfaro-Pozo [7], the analysis is related to a case study of the Nissan plant in Barcelona: an assembly line of nine types of engines grouped into three families: SUVs, Vans and Trucks (see an engine example in Fig. 3). The production line under study employs 42 operators work in shifts of 8 h, and the significant data of this case are the following:
There are 9 job types \((\left|I\right|=9\)) so that each job type corresponds to a type of engine.
The workshop (line) has 21 workstations (\(\left|K\right|=21\)) arranged in series.
In this work, we consider 23 engine demand plans \(\left|\mathrm{{\rm E}}\right|=23\) (see Table 3).
The daily demand is 270 jobs for all demand plans \(T \equiv D_{\varepsilon } = 270~{\text{jobs}}~\left( {\forall \varepsilon \in {\text{{\rm E}}}} \right)\).
The demand plans have been grouped into 7 categories (see Table 4).
The values of the processing times at normal work pace \(p_{{i,k}} \left( {\forall i \in I,\forall k \in K} \right)\) are between \(89{\text{s}}\) and \(185{\text{s}}\) (see Table 5).
Fig. 3
Nissan Pathfinder Engine. Characteristics: (i) 747 parts and 330 references, (ii) 378 elemental assembly tasks grouped in 140 production line tasks
Table 3
Daily demands by product type and plan \(\left( {d_{{i,\varepsilon }} } \right)\) for the 23 instances Nissan-9Eng.I \(\left( {\varepsilon \in {\rm E}} \right)\)
\(\varepsilon \in \mathrm{{\rm E}}\)
1
2
3
4
5
6
7
8
9
SUV
Van
Truck
Total
1
30
30
30
30
30
30
30
30
30
90
60
120
270
2
30
30
30
45
45
23
23
22
22
90
90
90
270
3
10
10
10
60
60
30
30
30
30
30
120
120
270
4
40
40
40
15
15
30
30
30
30
120
30
120
270
5
40
40
40
60
60
8
8
7
7
120
120
30
270
6
50
50
50
30
30
15
15
15
15
150
60
60
270
7
20
20
20
75
75
15
15
15
15
60
150
60
270
8
20
20
20
30
30
38
38
37
37
60
60
150
270
9
70
70
70
15
15
8
8
7
7
210
30
30
270
10
10
10
10
105
105
8
8
7
7
30
210
30
270
11
10
10
10
15
15
53
53
52
52
30
30
210
270
12
24
23
23
45
45
28
28
27
27
70
90
110
270
13
37
37
36
35
35
23
23
22
22
110
70
90
270
14
37
37
36
45
45
18
18
17
17
110
90
70
270
15
24
23
23
55
55
23
23
22
22
70
110
90
270
16
30
30
30
35
35
28
28
27
27
90
70
110
270
17
30
30
30
55
55
18
18
17
17
90
110
70
270
18
60
60
60
30
30
8
8
7
7
180
60
30
270
19
10
10
10
90
90
15
15
15
15
30
180
60
270
20
20
20
20
15
15
45
45
45
45
60
30
180
270
21
60
60
60
15
15
15
15
15
15
180
30
60
270
22
20
20
20
90
90
8
8
7
7
60
180
30
270
23
10
10
10
30
30
45
45
45
45
30
60
180
270
Table 4
Grouping of the 23 instances Nissan-9Eng.I into 7 categories of demand plans
Category
Plans
Type of demand plan
01
#1
Balanced demand for products
02
#2
Balanced demand for families
03
#3 to #5
Very low demand for a family
04
#6 to #8
High demand for a family
05
#9 to #11
Very high demand for a family
06
#12 to 17
Family demand in arithmetic progression
07
#18 to 23
Family demand in hypergeometric progression
Table 5
Processing time under normal operation \(\left({p}_{i,k}\right)\) in seconds of the 9 types of engines \(\left(i\in I\right)\) in the 21 workstations \(\left(k\in K\right)\) of the set of Nissan-9Ing.I
\(k\backslash i\)
1
2
3
4
5
6
7
8
9
Av
1
104
100
97
92
100
94
103
109
101
100.0
2
103
103
105
107
101
108
106
102
110
105.0
3
165
156
164
161
148
156
154
164
155
158.1
4
166
175
172
167
168
167
168
156
173
168.0
5
111
114
114
115
117
117
115
111
111
113.9
6
126
121
122
124
127
130
120
121
134
125.0
7
97
96
96
93
96
89
94
101
92
94.9
8
100
97
95
106
94
102
103
102
100
99.9
9
179
174
173
178
178
171
177
171
174
175.0
10
178
172
172
177
178
177
175
173
175
175.2
11
161
152
168
167
167
166
172
157
177
165.2
12
96
106
105
97
101
100
96
104
96
100.1
13
99
101
102
101
99
101
96
102
99
100.0
14
147
155
142
154
146
143
154
153
155
149.9
15
163
152
156
152
153
152
154
156
156
154.9
16
163
185
183
178
169
173
172
182
171
175.1
17
173
179
178
169
173
178
174
175
175
174.9
18
176
167
181
180
172
173
173
168
184
174.9
19
162
150
152
152
160
151
155
148
167
155.2
20
164
161
157
159
162
160
162
158
157
160.0
21
177
161
154
168
172
170
167
149
169
165.2
×
All the production plans shown in Table 1 have been used to carry out the computational experimentation developed in this work. As said, the total number of engines assembled in a working day is 270 in two shifts. The 7 categories that allow the grouping of demand plans are summarized in Table 4.
Meanwhile, the values of the processing times \({p}_{i,k}(\forall i\in I,\forall k\in K)\) for each job type and for each workstation are shown in Table 5.
5.2 Procedures and computational analysis
The compiled codes of the procedures that we have selected in this work are MILP (1 and 2) and MS-Q (running in Intel(R) Core (TM) i7-8750H CPU @ 2.21 GHz, 16 GB RAM, × 64 Windows 10 Pro). Table 6 shows the best results with respect to \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\) and CPU Time from MILP (1 and 2) and MS-Q procedures for the 23 datasets of the problem \(\varepsilon \in \mathrm{{\rm E}}\). In "Appendix I", the 46 best Quota-sequences obtained by MILP-2 and MS-Q are published.
Table 6
Results for \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\) (seconds) and \(Gap\) (in millionths) for Nissan-9Eng.I instances using MILP-1, MILP-2 and MS-Q
\(\varepsilon \in \mathrm{{\rm E}}\)
MILP-1
MILP-2
MS-Q
\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{1}\)
\(\mathrm{C}\mathrm{P}\mathrm{U}\)
\(LB\)
\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}\)
\(\mathrm{G}\mathrm{a}\mathrm{p}\)
\(\mathrm{C}\mathrm{P}\mathrm{U}\)
\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{3}\)
\(\mathrm{G}\mathrm{a}\mathrm{p}\)
\(\mathrm{C}\mathrm{P}\mathrm{U}\)
1
50,091
45.8
50,100
50,101
20
3600.6
50,101
20
176.8
2
50,174
15.2
50,180
50,180
0
366.7
50,180
0
130.8
3
50,301
10.3
50,303
50,303
0
37.9
50,303
0
15.5
4
50,167
13.6
50,170
50,170
0
38.6
50,170
0
213.0
5
50,379
9.9
50,385
50,385
0
45.7
50,385
0
73.6
6
50,202
14.3
50,202
50,202
0
14.1
50,204
40
2.9
7
50,395
8.3
50,397
50,397
0
33.4
50,397
0
180.1
8
50,123
12.4
50,126
50,128
40
3600.3
50,130
80
233.5
9
50,378
10.4
50,378
50,378
0
17.0
50,378
0
5.3
10
50,619
7.6
50,625
50,625
0
9.0
50,625
0
15.9
11
50,078
25.3
50,084
50,084
0
162.4
50,086
40
48.7
12
50,192
17.4
50,196
50,196
0
102.4
50,196
0
176.0
13
50,123
14.8
50,126
50,136
199
3600.3
50,136
199
12.7
14
50,218
10.1
50,223
50,223
0
134.7
50,224
20
48.7
15
50,242
10.5
50,242
50,242
0
105.0
50,242
0
175.7
16
50,118
55.8
50,123
50,123
0
160.3
50,128
100
129.0
17
50,269
10.6
50,273
50,273
0
74.0
50,275
40
4.3
18
50,273
14.3
50,273
50,273
0
15.1
50,275
40
8.3
19
50,475
8.1
50,481
50,481
0
7.8
50,481
0
15.0
20
50,089
96.1
50,100
50,100
0
65.2
50,100
0
48.1
21
50,307
13.8
50,307
50,307
0
10.5
50,307
0
5.4
22
50,539
7.3
50,545
50,545
0
9.3
50,545
0
31.9
23
50,151
11.0
50,157
50,157
0
44.0
50,158
20
24.3
Av
50,256.7
19.3
50,260.7
50,261.3
11.3
532.8
50,262.0
26.0
77.2
Max
50,619
96.1
50,625
50,625
199
3600.6
50,625
199
233.5
Min
50,078
7.3
50,084
50,084
0
7.8
50,086
0
2.9
Columns \(CPU\) show the CPU time (seconds) spent solving each instance
In Table 6, the column headings represent the following characteristics:
\(\varepsilon \in \mathrm{{\rm E}}\)
Identification number of the instances for Plan#1 to Plan#23
\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{1}\)
Optimal value of makespan for the \(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem obtained for MILP-1
\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}\)
Best makespan value for the \(\mathrm{H}\mathrm{e}\mathrm{i}\mathrm{j}\mathrm{u}\mathrm{n}\mathrm{k}\mathrm{a}-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem obtained for procedure MILP-2
\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{3}\)
Best makespan value for the \(\mathrm{H}\mathrm{e}\mathrm{i}\mathrm{j}\mathrm{u}\mathrm{n}\mathrm{k}\mathrm{a}-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem obtained for procedure MS-Q
\(LB\)
\({C}_{max}\) lower limit for the \(\mathrm{H}\mathrm{e}\mathrm{i}\mathrm{j}\mathrm{u}\mathrm{n}\mathrm{k}\mathrm{a}-Fm\)/\(block\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem obtained for MILP-1 or MILP-2 using the CPLEX solver
\(\mathrm{G}\mathrm{a}\mathrm{p}\)
Relative gap between \(C_{{{\text{max}}}}^{h} ~\left( {h \in \left\{ {2,3} \right\}} \right)\) and \(LB\) measured in millionths
The relative gap values (measured in millionths) between \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{k}\) and \(LB\) is calculated using formula (25).
MILP-1: Model \(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\): (i) Objective function for minimizing the \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\) value of the production sequence; (ii) implementation for IBM ILOG CPLEX solver (Optimization Studio v.12.2, win- × 86–64); (iii) maximum CPU time of 180 s allowed for solving each instance (23 instances). The average CPU time used by each demand plan to find the optimal solution is equal to 19.3 s. This procedure is used to determine adjusted lower bounds for the problem under study.
MILP-2: Model \(Hejunka-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) (this work): (i) Objective function for minimizing the \({C}_{max}\) value of the Quota production sequence; (ii) implementation for IBM ILOG CPLEX solver (Optimization Studio v.12.2, win- × 86–64); (iii) maximum CPU time of 3600 s allowed for solving each instance (23 instances). The average CPU time used by each demand plan to find the best solution is equal to 532.8 s.
MS-Q: Is the Multistart algorithm presented in this work, which is focused on minimizing the total completion time \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\) in Quota manufacturing sequences. The maximum number of iterations for each demand plan from Nissan-9Eng.I instances is equal to 20 with five candidate admission factors \(\alpha = \left( {0.11,~0.20,~0.33,~0.50,~1} \right)\), which generates in the constructive phase 1863 solutions and 14,110 improved solutions (improvement phase) in 115 executions. MS-Q uses on average a CPU time equal to 77.2 s to find the best solution for each demand plan and each admission factor \(\alpha \).
On the other hand, an analysis of Table 6 reveals the following:
Procedure MILP-1 obtains and ensures optimal solutions in all instances with 270 jobs (23 instances Nissan-9Eng.I) when the \(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem is solved (see column \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{1}\) in Table 6). The solutions obtained by MILP-1 do not necessarily satisfy the Quota property: MILP-1 violates the Quota property in 18 of 23 demand plans.
Procedure MILP-2 obtains and ensures optimal solutions in 20 of the 23 instances with 270 jobs when the \(Heijunka-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem is solved (see column \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}\) in Table 6). All the solutions obtained by MILP-2 satisfy the Quota property.
Procedure MS-Q obtains optimal solutions in 13 of the 23 instances with 270 jobs when the \(Heijunka-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem is solved (see column \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{3}\) in Table 6). All the solutions obtained by MS-Q satisfy the Quota property.
Regarding the value of objective \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\), on average, MS-Q solutions differ by 0.7 s from MILP-2, in a range of values between 0 and 5 s (see columns \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}\) and \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{3}\) in Table 6), when considering a 50,770 s workday to build 270 engines. Consequently, MS-Q solutions can be considered equivalent to MILP-2 from the perspective of the management of productive operations.
The average value of the relative gap between \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{2}\) and \(LB\) achieved by MILP-2 is 1.13E-05 in a range of values between 0 and 1.99E-04.
The average value of the relative gap between \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}^{3}\) and \(LB\) achieved by MS-Q is 2.60E-05 in a range of values between 0 and 1.99E-04.
The average CPU times used by MILP-1 (to determine lower bounds for the problem under study) are approximately 19.3 s for each instance of 270 jobs in a range of values between 7.3 and 96.1 s, when a maximum CPU time equal to 180 s is imposed on CPLEX to solve each instance for \(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem.
The average CPU times used by MILP-2 are approximately 532.8 s for each instance of 270 jobs in a range of values between 7.8 and 3600.6 s, when a maximum CPU time equal to 3600 s is imposed on CPLEX to solve each instance of the problem under study.
The average CPU time used by MS-Q is equal to 77.2 s within a range of values between 2.9 and 233.5 s, when 20 iterations are performed with the algorithm.
In average CPU times, MS-Q is 6.902 times faster than MILP-2.
In average relative gap, MILP-2 solutions are at 1.13E-05 of the lower bound while MS-Q solutions are at 2.60E-05 of that bound, which constitutes a technical tie.
For its part, Table 7 shows some properties on the performance of the MS-Q procedure, both in its construction phase and in its improvement phase, when the set of Nissan-9Eng.I instances is solved.
Table 7
Some properties of the performance of MS-Q with the set of instances Nissan-9Engine-I
In Table 7, the column headings represent the following characteristics:
\(\varepsilon \in \mathrm{{\rm E}}\)
Identification number of the instances for Plan#1 to Plan#23
\({\alpha }^{*}(\varepsilon )\)
Best admission factor in A1, \(\alpha \in \left\{ {0.11,~0.20,~0.33,~0.50,~1} \right\}\), for each \(\varepsilon \in \mathrm{{\rm E}}\)
\({r}_{mxs}^{*}(\varepsilon )\)
Utilization rate of \(\mathrm{M}\mathrm{A}\mathrm{X}\mathrm{S}\mathrm{A}\mathrm{T}\) procedure in A2 for the best solutions of each demand plan \(\varepsilon \in \mathrm{{\rm E}}\)
\({r}_{no\_Q}(\varepsilon )\)
Rate dissatisfaction of the Quota constraints (from A1) for the best solutions of each demand plan \(\varepsilon \in \mathrm{{\rm E}}\). It is measured as a percentage: \(\%{r}_{no\_Q}(\varepsilon )\). The maximum number of Quota constraints is: \(\left|I\right|\times T\equiv \left|I\right|\times D\)
Number of solutions improved by Local Search (BL1 to BL5) to get the best solution locally optimal of each demand plan \(\varepsilon \in \mathrm{{\rm E}}\)
Number of solutions improved by Local Search (BL1 to BL5) limiting the MS-Q procedure to a maximum 20 iterations, for each demand plan \(\varepsilon \in \mathrm{{\rm E}}\)
\({CPU}_{1}(\varepsilon )\)
CPU time (seconds) per iteration, limiting the MS-Q procedure to a maximum 20 iterations, for each demand plan \(\varepsilon \in \mathrm{{\rm E}}\)
5.3 Economic-productive feasibility study
In this subsection, we carry out an analysis of the results considering two aspects: economic and productive.
The first aspect aims to evaluate the economic savings in euros that result from transforming the original assembly line with a cycle time \(c = 175{\text{~}}s\) into a regular flow workshop in the context of the \(Fm\)/\(prmu\)/\(C_{{{\text{max}}}}\)/\(d_{i}\) problem.
The second aspect of the productive type is intended to measure the drop in engine production generated by the use of Heijunka concept, used in Just in Time production systems, when imposed on manufacturing sequences that satisfy the Quota property; in this case, we will use the \(Heijunka-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) model.
To carry out this analysis, the following hypotheses are taken into account:
h1.
The current engine assembly line is made up of 21 workstations arranged in series. At each workstation, a team consisting of two operators operates (42 operators in total).
h2.
The current assembly line has a daily production capacity equal to 270 engines. Each production day is divided into two work shifts and each work shift has a productive time equal to 7.05 h, after subtracting the scheduled rest times during the work day, the full duration of which is equal to 8 h per shift.
h3.
The cost of loss engine production [6] has been valued at \(\varphi =2.28757\) euros per productive second. The cost \(\varphi \) is calculated taking into account three factors: (i) the average value of a motor that is equal to € 4,000, (ii) the value added to the product by the assembly line that is equal to 10% of the value of the motor, and (iii) the cycle time of the line that is equal to 175 s, that is, \(c = 175~s\) and the temporary window is \(l_{k} = 175{\text{~s}}.\)
h4.
Assuming a cycle time \(c = 175~s\) and that the assembly line is made up of 21 stations arranged in series, the manufacture of the 270 engines requires a time equal to \(C_{{{\text{max}}}}^{{\text{0}}} = 50770\) seconds to complete the 270 jobs when there is no work in progress on the line (no-WIP). Therefore, the direct benefit provided by the line is equivalent to € 108,000 per day.
Under these conditions, the daily savings in euros \(G\left( \cdot \right)\) and the daily increases in the production of \({{\Delta }}P\left( \cdot \right)\) motors, achieved with the transformation of the current assembly line into a regular flow workshop, are shown in Table 8.
Table 8
Results corresponding to the savings in euros \(G\left( \cdot \right)\) and the increase in engine production \(\Delta P\left( \cdot \right)\) for Nissan-9Eng.I instances using procedures MILP-1, MILP-2 and MS-Q
\(\varepsilon \in {\rm E}\)
MILP-1
MILP-2
MS-Q
\(G(1,\varepsilon )\)
\({\Delta} P (1,\varepsilon )\)
\(G(2,\varepsilon )\)
\({\Delta} P (2,\varepsilon )\)
\(G(3,\varepsilon )\)
\({\Delta} P (3,\varepsilon )\)
1
1552.00
3.88
1529.14
3.82
1529.14
3.82
2
1362.29
3.41
1348.57
3.37
1348.57
3.37
3
1072.00
2.68
1067.43
2.67
1067.43
2.67
4
1378.29
3.45
1371.43
3.43
1371.43
3.43
5
893.71
2.23
880.00
2.20
880.00
2.20
6
1298.29
3.25
1298.29
3.25
1293.71
3.23
7
857.14
2.14
852.57
2.13
852.57
2.13
8
1478.86
3.70
1467.43
3.67
1462.86
3.66
9
896.00
2.24
896.00
2.24
896.00
2.24
10
345.14
0.86
331.43
0.83
331.43
0.83
11
1581.71
3.95
1568.00
3.92
1563.43
3.91
12
1321.14
3.30
1312.00
3.28
1312.00
3.28
13
1478.86
3.70
1449.14
3.62
1449.14
3.62
14
1261.71
3.15
1250.29
3.13
1248.00
3.12
15
1206.86
3.02
1206.86
3.02
1206.86
3.02
16
1490.29
3.73
1478.86
3.70
1467.43
3.67
17
1145.14
2.86
1136.00
2.84
1131.43
2.83
18
1136.00
2.84
1136.00
2.84
1131.43
2.83
19
674.29
1.69
660.57
1.65
660.57
1.65
20
1556.57
3.89
1531.43
3.83
1531.43
3.83
21
1058.29
2.65
1058.29
2.65
1058.29
2.65
22
528.00
1.32
514.29
1.29
514.29
1.29
23
1414.86
3.54
1401.14
3.50
1398.86
3.50
Average
1173.37
2.93
1162.83
2.91
1161.14
2.90
Maximum
1581.71
3.95
1568.00
3.92
1563.43
3.91
Minimum
345.14
0.86
331.43
0.83
331.43
0.83
In Table 8, the \(G\left( \cdot \right)\) and \(\Delta P\left( \cdot \right)\) values are determined according to (26) and (27).
The analysis of Table 8 allows to obtain the following conclusions:
The daily saving in euros, \(G(1,\varepsilon )\), achieved with the transformation of the current line in a flow shop \(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\), manufacturing 270 engines per day, is equal to € 1173.37 on average. Such savings are included in the interval [345.14, 1581.71], and their values depend on the demand plan used (\(\varepsilon \in \mathrm{{\rm E}}\)).
In case of having the same time to produce as the current one (i.e., \(C_{{{\text{max}}}}^{0} = 50770{\text{~s}})\). , the estimate of the average daily increase in engine production is \({{\Delta }}P\left( {1,\varepsilon } \right) = 2.93\), by transforming the line into a flow shop and assuming that the demand plans (\(\varepsilon \in {\text{{\rm E}}}\)) do no vary. These increases are included in the interval [0.86, 3.95], and their values depend on the demand plan used (see Fig. 4).
The transformation of the current line into a regular flow shop subject to Heijunka concept (\(Heijunka-Fm\)/\(prmu\)/\({C}_{max}\)/\({d}_{i}\)) leads to a maximum average saving equal to € 1162.83 per day (see average maximum between the columns \(G\left(2,\varepsilon \right)\) and \(G\left(3,\varepsilon \right)\) in Table 8) when 270 engines are manufactured per day. In this case, said savings are included in the interval [331.43, 1568.00] and their values depend on the demand plan used.
In the case of the Heijunka-flow shop, the estimate of the daily increase in engine production with respect to the current line is equal to 2.91 engines on average (see average maximum between columns \({\Delta }P\left(2,\varepsilon \right)\) and \({\Delta }P\left(3,\varepsilon \right)\) in Table 8), provided that the original production mix does not vary in the demand plans. Here, these increases (engines per day) are included in the interval [0.83, 3.92] (see Fig. 4).
Fig. 4
Daily increased in engine production, over that of the current assembly line, obtained with procedures MILP-1 and MILP-2 or MS-Q for the Nissan-9Eng.I instance set
×
Figure 4 reveals similar performance between the two types of flow shops analyzed, with respect to increased productivity on the assembly line.
In fact, for all demand plans, MILP-1 solutions (18 of which do not satisfy the Quota property) correspond to increases in productivity, since the values of \({\Delta }P\left(1,\varepsilon \right)\) are all positive. Taking into account that the average daily increase is equal to \({\Delta }P\left(1\right)=2.93\) engines, it turns out that the average increase in productivity is 1.09% when the current assembly line becomes a regular flow shop (\(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\)).
For its part, if it is imposed in the previous flow shop that also conforms to some requests of the Heijunka concept (\(\mathrm{H}\mathrm{e}\mathrm{i}\mathrm{j}\mathrm{u}\mathrm{n}\mathrm{k}\mathrm{a}-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\)), it also turns out that all the solutions obtained with MILP-2 and MS-Q correspond to positive values \({\Delta }P\left(2,\varepsilon \right)\) y \({\Delta }P\left(3,\varepsilon \right)\) for all demand plans. Therefore, the Heijunka-flow shop also promotes an increase in productivity with respect to the current assembly line, with an average increase in the order of 1.08%, considering the value \({\Delta }P\left(2\right)=2.91\) engines per day corresponding to MILP-2, or \({\Delta }P\left(3\right)=2.90\) engines per day corresponding to MS-Q.
Note that the solutions offered by MS-Q and MILP-2 (see Tables 6 and 8) are equivalent from a technical-productive point of view, since on average the difference between their respective times required to manufacture a total of 270 engines is equal to 0.7 s (i.e., 50,262.0–50,261.3) using sequences that satisfy the Quota property, this value is negligible compared to the current available time \(\left( {C_{{{\text{max}}}}^{0} = 50770{\text{~s}}} \right)\) to manufacture 270 engines, which corresponds to a working day with just over 14 operating hours equally distributed between two work shifts.
5.4 Advantages and disadvantages of using MILP and MS-Q procedures
The solutions offered by MILP-2 and MS-Q, for the set of Nissan-9Eng.I instances, can be considered technically equivalent in terms of the value of \({C}_{max}\) (see "Appendix I"); therefore, we can conclude that both procedures are equally valid to solve the problem \(Hejunka-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\). However, since these procedures are of a different nature, it is necessary to highlight some advantages and disadvantages in relation to the application of each of them.
In the specialized literature, most articles on the \(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\) use heuristic and metaheuristic methods. The new problem proposed in this paper is more complex than the \(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\), so there is no reason to rule out the use of heuristics to solve the \(Hejunka-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem (Laplace’s principle of insufficient reason). The use of Mixed Integer Linear Programming (MILP) for flow shop problems is less widespread for both reference instances and realistic cases.
MILP-2 uses the IBM CPLEX solver, which is commercial software that requires a license in its professional version. CPLEX incorporates the most efficient optimization techniques related to MILP, and its efficiency is widely recognized in the scientific field, requiring knowledge of modeling techniques. In contrast, MQ-S is simple and easy to implement.
MILP-2 is an application based on an exact procedure (MILP), while MS-Q is an approximation algorithm.
MS-Q is on average about 7 times faster than MILP-2 for the Nissan-9Eng.I instance set with 270 jobs and 21 machines.
MS-Q operates on the set of feasible solutions, and the CPU time to converge to a local optimum is predictable based on neighborhoods. For its part, the MILP technique, as a branch and bound procedure, operates with non-feasible solutions (non-integer solutions) and, therefore, the CPU time used to reach a local (or global) optimum is much less predictable. In fact, in this work, the standard deviation of the CPU time spent by MILP-2 is \({\sigma }_{MILP-2}^{CPU}=1190.63\), while for MS-Q it is \({\sigma }_{MS-Q}^{\mathrm{C}\mathrm{P}\mathrm{U}}=77.24\).
5.5 Implementation of solutions in a production line
Taking into account the previous results, our proposal is to transform the current assembly line, with fixed cycle time and closed stations, into a regular flow workshop with open workstations within the framework of the Heijunka concept; this proposal is based on two evidences: one of an economic nature and the other of an organizational and management nature.
The first evidence is the possibility of saving an average of € 1162.83 per day by manufacturing 270 engines of various types or, alternatively, the possibility of producing on average 272.91 engines per day (instead of 270) while maintaining the current working hours (14.103 h).
The second evidence is in the organizational advantages for the management offered by the level production both in the plans and in the sequences of mixed models.
The level production concept is inherent in Heijunka's ideology, and we have applied it here by enforcing the conformity of the Quota property with manufacturing sequences. Among the productive and administrative advantages offered by Heijunka are the following:
(1)
Reduction of the stock level of the types of engines and engine components (Parts).
(2)
Adjustment of production capacity to the demand for engines.
(3)
Reduction of delivery times in all phases of the production system.
(4)
Reduction of the volume of information to direct the operations of the production system.
(5)
Ability to react to fluctuations in demand, since the preservation of the production mix means keeping the manufacturing system at its center of gravity from the production-demand point of view.
Having seen the advantages that a Heijunka-flow shop offers compared to a mixed model assembly line from a productive point of view, it is worth asking how to implement a solution (\(\pi \left(T)=({\pi }_{1},.,{\pi }_{T}\right)\)) when the virtual barrier of setting the manufacturing rate by cycle time \(c\) is removed.
This seemingly harmless fact involves converting current workstations to open stations, leading to a release such that both the start and end of jobs on each workstation do not occur periodically according to the value of the cycle time \(c\) (v.gr. 175 s), but they occur at irregular intervals that will depend on the duration of each job and the times of completion of the jobs in the current station and in the previous one.
To implement a \(\pi (T)\) solution in the workshop, it is necessary that at least the following conditions are met:
c1.
The manufacturing sequence must comply with the standards established in the collective agreement between the employee and the company. Compliance with this condition is guaranteed because all processing times (see Table 5) have been calculated at normal work pace and the productive time to manufacturing 270 engines (14.103 h using two shifts) takes into account the scheduled rest and forced stop times within the law.
c2.
Workshop operators must be kept informed about the rhythm and the progress of production at their workstations: every operator should know the following data at the all times: (i) the engine type that reaches your workstation; (ii) the subset of tasks that makes up the job in progress; (iii) the start instant of the job in progress; (iv); the processing time required to complete the job in progress at normal work pace; and (v) the time available to carry out the job in progress.
Condition c2 can be easily achieved using technologies of Internet of Things (IoT) within the framework of Industry 4.0, implementing an information system assisted by wireless connection between the central computer from production management and a set of customized tablets (42 tablets to cover the 21 workstations).
In this way, the set of tablets will visually and acoustically report on production progress at all times and on all workstations. Consequently, all operators will automatically receive the following personalized signals:
1.
Audible and visual warning that indicates the beginning of a job.
2.
Accelerated audible and visual warning when the time available to complete a job is ending.
3.
Visual warning of the dynamic list of pending tasks on a job with the possibility that operator validates the concluded tasks and actualizes the list of tasks.
Updating activities are possible in our case, since a job is made up of 6 tasks on average and the processing times of the jobs are between 89 and 185 s (see Table 5), these times are sufficiently large to update the information in each workstation.
6 Conclusions
In this work, a new manufacturing sequence model is presented which incorporates some Heijunka properties from Just-in-Time into the \(Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem. This extension (\(Heijunka-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\)) arises from our concern to adapt academic problems to problems closest to industrial reality in the automotive sector.
The dimension of the mathematical model corresponding to the problem presented depends on the number of types of jobs, the number of workstations and the total demand for products (engines) in a sequencing horizon. For example, the MILP formulation requires at least 13,770 variables (2430 of them binary) and 25,682 constraints, for 9 types of jobs, 21 workstations and 270 products to be manufactured.
Two methods have been used to solve the new problem applied to a case study based on an engine assembly line. The first of them is based on Mixed Integer Linear Programming, and the CPLEX solver has been used solving all 23 realistic instances from the Nissan-9Eng.I set. The second method, with which the same instances have been solved, is a multistart procedure in whose constructive phase initial solutions are generated satisfying the Quota property, while in the second phase the solutions are improved using five neighborhood (three exchange and two insertion) and attending to the criterion of minimum total completion time \(\left( {C_{{{\text{max}}}} } \right)\).
Both procedures have been highly competitive with the new problem, since they have been able to optimally solve a high percentage of the instances using reasonable CPU times. Specifically, procedure MILP-2 obtains and ensures optimal solutions in 20 of the 23 instances with 270 engines using an average CPU time equal to 532.8 s for each instance with an average value of the relative gap between \({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\) and the best lower bound equal to 11.3 millionths. For its part, MS-Q has been able to obtain 13 optimum within 23 instances using an average CPU time equal to 77.2 s for each instance with an average \(Gap\) equal to 26.0 millionths. Therefore, it can concluded that both procedures are valid to solve the \(\mathrm{H}\mathrm{e}\mathrm{i}\mathrm{j}\mathrm{u}\mathrm{n}\mathrm{k}\mathrm{a}-Fm\)/\(prmu\)/\({C}_{\mathrm{m}\mathrm{a}\mathrm{x}}\)/\({d}_{i}\) problem with a dimension adjusted to the automotive industry. However, although the solutions offered by MILP-2 and MS-Q can be considered equivalent in terms of the value of the objective function, it can be stated that MS-Q beats MILP computationally, being 6.902 times faster in CPU time in the experimental framework of the present case study.
Regarding the transformation of the current assembly line into a Heijunka-flow shop, the economic-productive feasibility study reveals that it is possible to save an average of € 1162.83 per day by manufacturing 270 engines or, alternatively, that it is possible to produce 3 more engines per day with the current working hours.
Finally, for future lines of work, we propose to incorporate in the presented model other productive concepts such as the activity factor of the operators and the possibility of blocking the productive flow between the workstations, as well as the incorporation of some desirable properties in the workloads of the manufacturing sequence.
Acknowledgements
This work has been funded by the Ministry of Economy and Competitiveness of the Government of Spain through project OPTHEUS (ref. PGC2018-095080-B-I00), including European Regional Development Funds (ERDF).
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Appendix I: Best sequences for Heijunka—\(\boldsymbol{F}\boldsymbol{m}\)/\(\boldsymbol{p}\boldsymbol{r}\boldsymbol{m}\boldsymbol{u}\)/\({\boldsymbol{C}}_{\boldsymbol{m}\boldsymbol{a}\boldsymbol{x}}\)/\({\boldsymbol{d}}_{\boldsymbol{i}}\) with the set of instances Nissan-9Eng.I
