Simple Assembly Line Balancing Problem with Power Peak Minimization

According to the International Energy Agency, in 2014 the industrial sector was responsible for 36% of the global total final energy consumption (TFEC), and since then its energy consumption has grown by 1.5% annually [1]. Hence, it is expected that in the future the most consistent reduction of greenhouse gas (GHG) emissions will come from an improved energy efficiency of industries [2]. Moreover, this period represents a transition phase for the industrial sector. The forth industrial revolution or Industry 4.0 will respond to economical, technological, organizational, societal and environmental issues. Among the objectives due to the environmental concern is the reduction of carbon footprint by optimizing the energy consumption. Therefore, it is important to rise awareness of the necessity to control the related consumption of manufacturers, since the power demand and energy consumption are steadily increasing.

In order to address this problem, one of the existing solutions is to reorganize the energetic consumption in order to obtain a lower power peak. The growing attention paid in the last decades to energy-aware manufacturing and production systems has led to an increased scientific effort to design decision support methods capable of achieving an optimized energy management. However, the number of works dealing with energy-driven optimization of scheduling or line balancing in manufacturing systems was still relatively scarce only a few years ago, as pointed out by [3].

In this paper, a new Assembly Line Balancing Problem with power peak minimization is considered. The rest of the paper is organized as follows. Section 2 introduces the literature review. Sections 3 and 4 present the new ALB problem and an integer linear program for it. Section 5 analyses the results of numerical tests. Finally, Sect. 6 presents the conclusion and future research perspectives.

Assembly line balancing (ALB) problems are among the most investigated optimization problems arising in production systems. ALB problems aim to optimally assign the elementary tasks involved in the assembly of a series of products to a set of workstations of a production line while complying with precedence constraints among tasks. These problems occur during the design of a production system and determine some of its main features, e.g. cycle time and number of workstations. The simplest and most studied variant is the Simple ALB Problem (SALBP) [4], in which the line is paced and synchronous, task process times are deterministic and independent of workstations and only one product is considered. In the case of type I SALBP (SALBP-1), the number of workstations m has to be minimized, given the cycle time c; the minimum c for a given value of m is sought for in type II SALBP (SALBP-2); finally, SALBP-E (efficiency) aims at minimizing the product \(c\cdot m\), or equivalently the total idle time, while SALBP-F (feasibility) tries to find out whether given values for both c and m admit a feasible solution. Despite its simple statement, SALBP is NP-hard and remains a challenging problem [5] and best known solution approaches are relatively recent [6,7,8]. A huge literature exists concerning ALB problem variants issued from several different application contexts. For more in-depth reading on ALB problems, the reader is referred to the excellent literature review of [9]. Assembly line design problems are also worth mentioning. In them, some special equipment must be assigned to workstations to enable them to perform tasks, as it is the case with robots in the Robotic ALB (RALB) [10].

For what concerns ALB problems with energy-driven optimization criteria, as far as the authors are aware of, few works can be found to date. In [11], a two-sided RALB is proposed, along with a Mixed-Integer Linear Programming (MILP) formulation. A simulated annealing-based metaheuristic algorithm is yielded to seek for Pareto-optimal solution w.r.t energy consumption and cycle time. In [12], two evolutionary algorithms, namely a Particle Swarm Optimization (PSO) and a Differential Evolution algorithm, are used to minimize the energy consumption of a U-shaped robotic assembly line. A RALB variant minimizing the total energy consumption, a Nonlinear Programming formulation and a PSO-based approach are the main contributions of [13]. The benchmark instances for type II RALB of [14] are used to test the effectiveness of the proposed approach.

This short literature review shows that few works exist that consider energy on a strategic level, i.e. since the design phase, in a production system, and in those works the concerned aspect is the minimization of energy consumption of equipment associated with workstations. The authors are not aware of works that tackle the power peak involved in the processing of the production tasks at a strategic level. However, power peak minimization or a power peak constraint can be found in works dealing with other production-related optimization problems at a more tactical or operational level, especially in scheduling.

In flow-shop scheduling, [15] proposes a mixed-integer linear program (MILP) to minimize energy consumption, makespan and carbon footprint, while [16] resort to a heuristic to minimize total tardiness and makespan of a flexible flow-shop, both under a power peak constraint. The scheduling of a job-shop with makespan minimization and power peak is addressed by [17] and tackled by means of a MILP, while [18] introduces a power peak constraint in a production system with parallel machines and proposes a heuristic method. Finally, [19] tries to minimize energy cost in a job-shop under makespan and power peak constraints. In this work, a new ALB problem is addressed which aims at minimizing the overall power consumption peak and does not seem to have yet received attention in the literature. An Integer Linear Program is proposed and tested.

In the following the Simple Assembly Line Balancing Problem with Power Peak Minimization (SALB3PM) is introduced, along with the related notations and an example to help the reader understand the key aspects of power peak minimization.

The classic SALBP consists in assigning the tasks of a set \(\mathcal {O}\) to the workstations of a set \(\mathcal {M}\) of a paced, synchronous production line. Predecence constraints are defined that force each task \(j\in \mathcal {O}\) to wait the end of all its direct predecessors before its processing can start: the notation \(i\prec j\) indicates that i is such a direct predecessor. Each task j features a processing time \(t_j\) which is constant and independent of workstations. The goal is usually to optimize the cycle time or the number of workstations, the other being given, in such a way that precedence constraints are fulfilled, tasks are not preempted and each workstation processes at most one task at a time all along the time horizon. It is worth noting that the classic SALBP disregards scheduling aspects, because once tasks are optimally assigned to workstations, they can be scheduled at any date along the cycle time. This does not change the solution value, nor it affects its feasibility, as long as precedence constraints among tasks on the same workstation are complied with. In the SALB3PM, similarly to what is done in the SALBP-F, both the number of available workstations \(m=|\mathcal {M}|\) and the maximum allowed cycle time c are given. Moreover, each task j features a power consumption \(W_{j}\), constant and independent of workstations. The goal becomes to find a feasible assignment of tasks to workstations s.t. the highest peak of the overall power consumption profile is minimized. This objective requires to integrate scheduling decisions in the SALB3PM, thus asking for dedicated decision variables. Most of all, the strong connection of this further decision layer with the other classical decisions make the SALB3PM harder than the SALBP.

Figure 1 illustrates the impact of power peak minimization by comparing two feasible solutions for a SALB3PM instance with cycle time \(c=18\), \(m=3\) workstations and \(|\mathcal {O}|=9\) tasks. The leftmost one is a generic solution that displays a very fluctuating overall power consumption profile. The rightmost one is an optimal solution, i.e. in which the maximum value of global power consumption over the time horizon is minimized: the overall consumption profile is much more smoothened and a power peak reduction of 36.6% is achieved.

A generic (left) and an optimal (right) solution of a SALB3PM instance with \(c=18\), \(m=3\), \(|\mathcal {O}|=9\). Dashed lines separate the schedule of workstations. Numbered boxes represent tasks: their width, height and position stand for associated processing times, power consumption values and starting times. A thick curve depicts the evolution of the overall power consumption profile.

Full size image

In this section an Integer Linear Programming (ILP) model for the SALB3PM is presented. The model is time-indexed, i.e. its main feature is that the time horizon is subdivided in unit time slots and the variables describing the scheduling of tasks have a time index. This allows a detailed representation of the processing of tasks and hence of the cumulative power profile all along the time horizon.

Let and denote respectively the entire set of time slots, and the available time slots for the start of task i. The model has one integer nonnegative variable and two sets of binary variables:

\(\blacktriangleright \) :

power peak variable \(W_{\!\max }\), an upper bound on the power consumption peak;

\(\blacktriangleright \) :

assign variables \(X_{i,k},\,i\in \mathcal {O},\,k\in \mathcal {M},\,X_{i,k}\!=\!1\!\Leftrightarrow \,\)task\(\,i\) assigned to workstation k;

\(\blacktriangleright \) :

trigger variables \(S_{i,t}\), \(i\in \mathcal {O}\), \(t\in \mathcal {T}^{i}\), \(S_{i,t}=1\Leftrightarrow \) processing of task i starts at time slot t of each cycle.

The proposed model is the following:

(2)

(3)

(4)

(5)

(6)

(7)

(8)

Constraints (2)–(4) are classical SALBP constraints. Each task j is assigned to exactly one workstation k by (2), and each \(i\in \mathcal {O}\) s.t. \(i\prec j\) is assigned to k or one of the upstream workstations by precedence constraints (4). Tasks assigned to one workstation have the sum of their processing times bounded by c due to (3).

Constraints (5)–(8) are specific to SALB3PM. Each task j is processed at some date \(t\in \mathcal {T}^{j}\) due to (5), which ensures its termination within given cycle time c. Constraints (6) add to (4) in enforcing precedence. If tasks i and j, \(i\prec j\), are assigned to the same workstation, then (6) (jointly with (5)) force i to start at least \(t_i\) time slots sooner than j. Otherwise (6) are redundant as the right hand side is greater or equal than one. Relations (7) impose to have at most one task at a time running on the same workstation at date t of each cycle. Indeed, term \(\sum _{\tau =t-t_i+1}^{t}S_{i,\tau }\) is 1 if task i has started at a date , in which case it is still running at date t. Hence, (7) state that either both i and j are running at date t, which forces \(X_{i,k} + X_{j,k}\le 1\), or both are assigned to \(k\in \mathcal {M}\), i.e. \(X_{i,k} + X_{j,k}=2\) and at most one of the two can be running at date t.

Finally, (8) state that for each date t the sum of the power consumption of the currently running tasks is bounded by \(W_{\!\max }\). This is because the left hand side of (8) represents the overall power consumption at date t of each cycle. Along with the objective function (1), this smooths the overall power consumption profile, as shown in Fig. 1.

In this section, the computational session conducted to assess the performance of the proposed ILP model is illustrated. The model is implemented in CPLEX 12.6 and solved by Branch&Bound (B&B). Tests are run on a Intel Core i7-5500U 2.40 Ghz machine with 15.55 Gb RAM. All instances are given a 3600 s time limit.

A testbed set of 19 SALB3PM instances is generated, inspired from 15 benchmark SALBP-1 datasets and 4 benchmark SALBP-2 datasets^{Footnote 1} and completed with task power consumption values \(W_{i}\) randomly generated from the uniform distribution U(5, 50). In the original datasets the number of tasks varies between 7 and 30, and either c is given and m is the computed optimal number of workstations, or m is given and c is the optimal cycle time. This guarantees the feasibility of the derived SALB3PM instances. From each SALB3PM instance, another one is obtained with cycle time augmented by 30% and rounded up, so as to stress the performances of the time-indexed model. To assess the power consumption improvement, a heuristic solution is generated by:

\(\blacktriangleright \) :

solving (B&B) a reduced model (1)–(4) (i.e. removing scheduling constraints),

\(\blacktriangleright \) :

sorting tasks on each workstation so as to comply with precedence constraints,

\(\blacktriangleright \) :

schedule tasks at the earliest date, i.e. without idle times between them.

Table 1 reports the results for each instance. \(W_{\!\max }\) is the optimal power peak value, while \(T/(\%)\) is the computational time (in seconds) to compute it, or the optimality gap still to close at time limit. \(W^{_H}_{\!\max }\) is the value of the heuristic solution: the time to compute it is always less than 1s and thus neglected. Terms \(\overline{W^{_H}_{\!\max }}\), \(\overline{W_{\!\max }}\), \(\overline{T/(\%)}\) have the same meaning w.r.t longer cycle time \(\overline{c}=\lceil 1.3\cdot c\rceil \). Table 1 shows that in 23 instances out of 38 an optimal solution is achieved within time limit. In most cases only few seconds are needed, except in six cases which require more than 200 s. This is acceptable considering the strategic nature of the problem. For such instances, an average power peak gain of −19.8% is achieved w.r.t the heuristic solution (with \(\frac{W_{\!\max }}{W^{_H}_{\!\max }}<1\) in 20 cases out of 23), in which scheduling decisions are greedy. In particular, the average gain is −22.5% for instances with high cycle time.

In 8 out of the remaining 15 instances, the B&B finds a feasible solution but the optimality gap is greater than 0 at time limit, even though less than 2.5% in five cases (6.31% on average). This is probably caused by the increased computation hardness, due to the growing number of tasks, and also the larger search space for instances with longer cycle time. Nevertheless, a considerable average power peak improvement of −27.1% is obtained w.r.t the heuristic solution.

In the remaining 7 instances, no feasible solution can be found. The heuristic solution can then be used as a warmstart for the B&B, as shown in Table 2.

In two cases, an average power peak improvement of −15.8% is achieved. By considering the overall behavior of the \(\frac{W_{\!\max }}{W^{_H}_{\!\max }}\) ratio, the optimality gap still to close at time limit is probably mostly due to the distance between \(W^{_H}_{\!\max }\) and the optimal value. This is promising in terms of further power peak gains that can be potentially obtained.

Finally, the results for the 9 instances for which an optimal solution is found with both c and \(\overline{c}\) show that the longer cycle time allows an average power peak gain of −21.6%. This suggests that from an industrial point of view it may make sense to decrease production pace as the consequences in terms of power consumption may be considerable.

In this work, a new Assembly Line Balancing (ALB) problem, the Simple Assembly Line Balancing Problem with Power Peak Minimization (SALB3PM), is studied in which the overall power consumption peak is minimized. The scheduling aspects that must be taken into account make this problem harder than classical ALB problems. An Integer Linear Program is proposed and tested on benchmark instances completed with power features. Preliminary results show that considerable gains can be achieved in terms of power consumption, and thus that SALB3PM deserves attention from researchers. In particular, it seems promising to study the extent of the interaction between balancing and scheduling decisions. This could lead to decomposition-based efficient metaheuristic approaches to hopefully deal with real-world instances.