Assembly line balancing problems aim to assign production tasks to workstations or people while satisfying some constraints and optimizing various criteria such as production rate or number of workstations needed. One specific instance is Simple Assembly Line Workload Smoothing Problem (SALBP-WS) that focuses on smoothing workloads of all workstations. This is important for establishing equity among workers or maintaining sustainable conditions for workstations. In this work, we develop several Answer Set Programming encodings for solving SALBP-WS. The performed experiments showcase better scalability results compared to problem specific exact methods based on branch and bound technique. Additionally, we propose a new criterion that handles the workstation idle times hierarchically, as a measure of smoothness of an assignment.
Another variant of SALBP is the workload smoothing problem (SALBP-WS), which is NP-hard [1]. SALBP-WS is an optimization problem based on SALBPF and aims at finding a feasible assignment such that resulting workloads of workstations are balanced as much as possible. This is important for establishing equity among workers or maintaining sustainable conditions for workstations. In this work, we are concentrating on the SALBP-WS.
Answer Set Programming (ASP) is a declarative problem solving paradigm with roots in Knowledge Representation and Reasoning (KRR). The simple but powerful language of ASP backed with highly efficient solver implementations make it applicable to various problems from broad range of domains [4, 6].
We developed a succinct ASP encoding of the SALBP-WS thanks to some powerful features of the ASP language like aggregates and optimization statements. To the best of our knowledge, this work is the first application of ASP to the problem. The resulting logic program can also be a foundation for other ALBPs. The experiments we have performed showcase better scalability results compared to problem specific SALBP-WS solvers.
Additionally, we propose a novel optimization criterion for the SALBP-WS to measure the smoothness of an assignment. Our motivation is to ease the burden on the ASP solver of large numbers appearing as optimization values in other criteria. The new hierarchical idle times (HIT ) criterion aims to minimize idle times of workstations hierarchically. The use of HIT in our encoding leads to significant improvement in the solving performance. Apart from this, HIT can be useful in general for ALBPs.
In what follows, we formally define the SALBP-F and SALBP-WS. In Section 3, we describe our ASP encodings. Several experiments are performed using the openly available problem instances and the results of these are explained in Section 4. Finally, we conclude with discussion and future line of research. 2
First, we define the feasibility version of the problem. Next, we cover the SABLPWS when an optimization function based on various smoothness criteria is added on top of the feasibility problem. 2.1
The Simple Assembly Line Balancing Feasibility Problem (SALBP-F) Consider n tasks and let T be the set ft1; : : : ; tng of all these tasks. For a given task t, t(t) gives the amount of time, which is named as task time, needed by any workstation for fully processing t. We assume all workstations are equally equipped and a task can be processed by any workstation. Considering a single-model assembly line with m workstations, let S be the set fs1; : : : ; smg of all workstations. Note that workstations are organized sequentially along the assembly line. Let i be the function that gives the order of a workstation in the line. The common setting adopted in open datasets of the literature is assigning positive integers as ids of workstations in a way that the one with 1 as an id is the first workstation in the assembly line. Following this setting, i(sj) = j. In a running assembly line an end product is produced at the end of each cycle. Let c be this cycle time. The main task of an assembly line balancing problem is to assign a task to a workstation. Let xts be a decision variable such that xts = 1 whenever task t is assigned to workstation s and xts = 0 otherwise. The workload of a workstation is the total time needed for processing all tasks assigned to it. Considering the line balancing denoted by assignment decision variables, the workload time of a workstation s 2 S is calculated by the following equation.
wl(s) = X t(t) xts
(
Additionally, tasks have to be performed in some predefined order, which can be due to the nature of the product or the organizational constraints, such that no task can be performed unless all of its predecessors are complete. This condition and the fixed order of workstations in the assembly line constrains the assignment of tasks to workstations. To this end, we have an input directed acyclic graph P = (T ; E), which is called the precedence graph. The vertices are all the tasks and an edge (u; v) 2 E denotes that i(a) i(b), where u; v 2 T , xau = 1 and xbv = 1. Recall that i(a) designates the order of a in the assembly line via an ordinal number.
Now, we can formally define SALBP-F. Given T , S, c and P, the SALBP-F problem aims to find an assignment of tasks to workstations via setting xts = 1 or 0 for all t 2 T and s 2 S while satisfying the following constraints.
X xts = 1 s2S X t(t) xts t2T
(8t 2 T ) c
(8s 2 S) X i(a) xau
X i(b) xbv
(8u; v 2 T ; (u; v) 2 E) a2S b2S
The constraint (
The Simple Assembly Line Workload Smoothing Problem (SALBP-WS) The SALBP-WS is an optimization problem based on SALBP-F. It is also known as the Type III problem [5]. The SALBP-WS aims at finding an assignment such that resulting workloads of workstations are balanced as much as possible given the assignment satisfies the constraints of the feasibility variant SALBP-F.
An assignment is balanced for workstations when their workloads are equal or close to each other as much as possible. In order to achieve this optimization objective, various optimization criteria have been proposed. The two prominent ones are smoothness index and mean absolute deviation of workloads. The smoothness index (SI) value is calculated by the sum of squared differences between workstation workloads and the cycle time as shown in the equation below [1, 10].
SI =
X (c wl(s))2
min SI s2S The mean absolute deviation of workloads (MAD) value is calculated by the sum of absolute deviations of workstation workloads from the average workload (i.e., the sum of all task times divided by the number of workstations) [11].
M AD = X wl(s) s2S
P t2T t(t) jSj min M AD
The SALBP-WS utilizing SI as the optimization criterion aims to minimize
the SI value of a feasible solution. Hence, its definition is the addition of the
whole objective (
The following running example is selected from [2].
Example 1. In an single-model assembly line there are 5 workstations; S =
fs1; : : : ; s5g and their order is given by i(sx) = x. The production needs 10 tasks
T = f1; : : : ; 10g, where the precedence graph P is depicted in Figure 1. The
task times are also given in upper right corners of task nodes in P (for instance,
t(
1
Considering the assembly line configuration given in Example 1, a solution for
the SALBP-F is shown diagrammatically in Figure 2. The solution assigns f3; 4g,
f1g, f2; 5g, f6; 7; 8g and f9; 10g to workstations s1; s2; s3; s4 and s5, respectively.
Consequently, the workload times wl(s4) = 11 and wl(s5) = 11 (i.e., they
have 0 idle times), and for the other workstations wl(s1) = 9, wl(s2) = 6 and
wl(s3) = 10 (i.e., they have 2, 5 and 1 idle times, respectively). Note that SI value
of the feasible solution shown in Figure 2 is 22 +52 +12 +02 +02 = 30. Additionally,
its M AD value is j9 9:4j+j6 9:4j+j10 9:4j+j11 9:4j+j11 9:4j = 7:6. It is
not a SI optimal solution. Figure 3 depicts a solution for the SALBP-WS problem
of the assembly line configuration given in Example 1. Note that the workstations
have 2, 1, 1, 4 and 0 idle times, respectively. The SI value of this optimal solution
is 22 + 12 + 12 + 42 + 02 = 22. Regarding the M AD criterion, the solution in
Figure 3 has j9 9:4j + j10 9:4j + j10 9:4j + j7 9:4j + j11 9:4j = 5:6 as the
M AD value. Actually, it is also an optimal solution for the SALBP-WS problem
when M AD is used as the criterion.
In our initial experiments we have observed that large numbers as optimization
values of SI and M AD criteria (especially the quadratic value in (
HIT = ham; : : : ; a1i
s.t. ai = j fsxjc
wl(sx) = ig j; i
c
(
When we want to utilize the HIT criterion, the SALBP-WS problem is modeled as a multi-objective lexicographical optimization problem unlike the cases in SI and M AD. Note that ASP has the capacity of modeling such multi-objective optimization problems. We try to minimize the HIT value of an assignment in a lexicographical way such that along the optimization minimizing the number of workstations with i idle times is given more priority than minimizing the number of workstations with j idle times where j < i. Formally, an assignment with a HIT value ha1; : : : ; ai; : : : ; axi, is better than an assignment with a HIT value hb1; : : : ; bi; : : : ; bxi given that ak = bk for all 1 k < i and ai < bi.
Hence, SALBP-WS can also be modeled by adding the following optimization objective to the setting of SALBP-F.
lexmin HIT
(
For Example 1, the solution shown in Figure 3 is also an optimal solution when HIT is used as the criterion. Note that the HIT vector of this optimal solution is h1; 0; 1; 2i. In order to easily compare with the HIT value of the solution shown in Figure 2, one can also see h0; 1; 0; 1; 2i as the HIT value of the optimal solution since there are 0 workstations with an idle time of 5. 3
In this section, we first encode SALBP instances. Then, we explain the encoding of the SALBP-F variant. With the addition of encodings for smoothness criteria on top of the SALBP-F encoding, we complete our SALBP-WS encoding. For the syntax and semantics of the language used in encodings, one may refer to [3]. Additionally, detailed information about ASP based problem solving paradigm and the ASP solver clingo can be found in [7]. 3.1
The Listing 1.1 gives an instance encoding for Example 1 given in Section 2.
1 # const cycletime =11.
3 task (
task (
task (
task (
task (
precedence (
precedence (
precedence (
Listing 1.1. Encoding of the SALBP instance given in Example 1
The cycle time c = 11 is represented by the cycletime constant in Line 1. The decision of making c an ASP constant is to facilitate easy testing by trying different cycle time values in the clingo command line. The tasks and workstations in an instance are represented by ASP facts task/2 and workstation/1, respectively, in the following form: task(t,i) s.t. t 2 T ; i = t(t) and workstation(i(s)) s.t. s 2 S. For the sake of simplicity in encodings and the common way of naming in open datasets, we use the order i(S) of a workstation S as its identifier. The tasks and workstations of Example 1 are listed in Lines 3–4 and Lines 10–11, respectively. The precedence graph of an instance is represented by precedence/2 facts of form precedence(u,v) s.t. (u; v) is an edge of P. The facts in Lines 6–8 represent the precedence graph in Figure 1.
Although the instance format is developed specifically for SALBP-F and SALBP-WS instances, it can also be utilized for other SALBP variants. 3.2
Having represented a SALBP instance in ASP, we now encode the constraints of the SALBP-F. The assignment of a task to a workstation is represented by instances of the binary predicate assignment/2 in the form assignment(s,t) s.t. s 2 S; t 2 T . Given a task t and a workstation s, if the atom assignment(s,t) is in an answer set (or, if it is true), the SALBP-F solution corresponding to the answer set must have xts = 1. Otherwise, the solution must have xts = 0 (i.e., if the atom is not in the answer set). 1 { assignment (W ,T) : workstation (W )} = 1 :- task (T ,C ). 3 :- # sum {C ,T: assignment (W ,T), task (T ,C )} > cycletime , 4 workstation (W ). 6 :- precedence (X ,Y), assignment (W1 ,X), assignment (W2 ,Y), W1 > W2 . 8 # show assignment /2.
Listing 1.2. Encoding of the SALBP-F
The rules in Listing 1.2 comprise the ASP encoding of SALBP-F. Based on
the generate-and-test technique, a commonly used encoding technique in ASP [7],
the choice rule in Line 1 generates the search space based on xts decision variables
of SALBP-F. The same rule also represents the constraint (
Let be the encoding of SALBP-F composed of rules in Listing 1.2. When
we run clingo with the program and the instance rules in Listing 1.1 as input,
one answer set we get is the following one.
assignment (
Listing 1.3. Encoding of the SI criterion for SALBP-WS
With the help of the #sum aggregate, the rule in Lines 1–2 finds the workload of
each workstation. An atom workload(w,l), which is generated by the rule as an
instance of the workload/2 predicate, represents that the workload of workstation
w is l, i.e., wl(w) = l. A careful reader may notice the ‘cycletime>=L’ condition
in Line 2 is not necessary considering the SALBP-F constraint in Lines 3–4 of
Listing 1.2. Although it is redundant w.r.t. the semantics of the program, it
improves the grounding performance of clingo by avoiding the generation of
many futile ground instances of the respective rule (viz., ground rules with head
atoms such as workload(
Let SI be the SALBP-WS encoding composed of the SALBP-F encoding in
Listing 1.2 and the encoding of SI criterion in Listing 1.3. When we run clingo
with SI and the instance in Listing 1.1 as input, we get the following output.
Answer : 1
assignment (
Encoding M AD. Similar to the encoding of the SI criterion, we can encode the
M AD criterion in ASP. The ideal average workload of each workstation calculated
in (
X t(t) :
t2T
(
s2S
P M AD = X
wl(s) s2S t2T t(t) = X jSj s2S wl(s)jSj
P
t2T t(t) jSj = jSj s2S 1 X wl(s)jSj
X t(t) t2T Hence, the objective of min M AD = min Ps2S wl(s)jSj P t2T t(t) .
tu
One may get tempted to minimize Ps2S wl(s) as the optimization objective,
considering other parts of the equation (
Using Lemma 1, the rules in Listing 1.4 encode the M AD criterion and the respective objective function. 1 totaltask ( TT ) :- TT = # sum {C ,T : task (T ,C )}. 2 numworkstation ( NW ) :- NW = # count {W : workstation (W )}. 4 # minimize {|( L*N)-T|,W : workload (W ,L), totaltask (T), 5 numworkstation (N )}.
Listing 1.4. Encoding of the M AD criterion for SALBP-WS
The rules in Lines 1–2 calculate the number of workstations and total task time.
The #minimize statement in Line 4–5 represents the objective function (
Let MAD be a SALBP-WS encoding composed of Listing 1.4, Listing 1.2
and Lines 1–2 of Listing 1.3 (the definition of workload predicate). Given the
program MAD and the instance Listing 1.1, clingo finds an optimal answer set
that corresponds to the optimal SALBP-WS solution given in Figure 3.
Encoding HIT . The rules in Listing 1.5 encodes the HIT criterion (
idletime (W ,L), levels (L) }.
Listing 1.5. Encoding of the HIT criterion for SALBP-WS
Let HIT be the SALBP-WS encoding composed of Listing 1.2 and Listing 1.5. Running clingo with HIT and the problem instance Listing 1.1, we can solve the SALBP-WS for Example 1 and get the optimal solution given in Figure 3. 4
We have conducted several experiments to analyse performance of the ASP encodings SI ; MAD and HIT defined in Section 3.3. To this end, we used several benchmarks from a dataset mentioned in [13] and openly available from https://assembly-line-balancing.de/. All the experiments have been performed in a Linux machine with Intel E5-2630@2.20GHz CPU. For computing optimal answer sets, we have used clingo version 5.4.0 with 6GB as the memory limit and 600 seconds as the time limit.
The results of the ASP encodings are shown in Table 1. Instances of the experiment are partitioned into groups with a fixed number of tasks and a fixed precedence graph. For instance, all instances of the Mitchell group have 21 tasks (shown by the jT j column) and the same precedence graph. They may vary in the number of workstations (shown by the jSj column) and the cycle time (shown by the c column). The results of each encoding are under SI ; MAD and HIT columns. For each encoding, we report the SI (shown by the SI column) and M AD (shown by the M AD column) values of the best solution found within the time limit. By doing so, we aim to investigate whether one can select any criterion without significant deviation in terms of quality or not (this is discussed further below). If clingo has proved that the best found solution is indeed an optimal one we report the time used (shown by the Time column) and otherwise (i.e., clingo does not find an optimal solution within 600 seconds), we report as the time value.1
One main result is that when the number of tasks increases with a usual consecutive increase in cycle time, instances become much harder to solve. The
SI encoding struggles earlier than the two other ones and in total finds less
number of optimal solutions. The MAD and HIT encodings scale better. We
think clingo has difficulty in minimizing big quadratic numbers in (
Another important result is about the SI and M AD values of the optimal solutions. Considering the instances where any two encodings find an optimal solution, the corresponding SI and M AD values of these solutions are the same except a few cases. For instance, Gunther 35, 7, 81 is one exception where the optimal solution found by MAD has SI value of 1198, which is slightly more than 1186 the SI value of the optimal solutions found by SI and HIT . This consistent agreement on SI and M AD values of all encodings shows that one can select any of the encodings or optimization criteria. This is a significant observation since the recent studies in the research community focus only on SI, while another criterion may improve computation performance without any significant deviation in terms of quality. We have experienced exactly this case for our encodings where MAD and HIT perform clearly better than SI .
Unlike the other SALBP types, studies on SALBP-WS are scarce. Being an intractable problem, most of the efforts to solve the SALBP-WS focus on heuristic methods [11, 10, 5]. In [1], however, an exact method of solving SALBPWS with the SI criterion is studied. Basically, they have implemented a problem specific search algorithm based on branch and bound technique. Neither their implementation nor the instances they used are openly available.2 However, it is explicitly stated in [1] that their algorithm can solve instances with up to 29 tasks. Our way of solving SALBP-WS via ASP is also an exact method and the results in Table 1 show that our encodings scale better w.r.t. the number of tasks.
Another exact method for solving SALBP-WS is [9]. They have also implemented a branch and bound based algorithm that utilizes heuristics for computing lower and upper bounds. Their empirical studies uses 117 instances from the same ALBP dataset website we used. We have also tested our ASP encodings with these 117 instances and the results are reported in Table 2. The number of 1 We observed that grounding times of clingo are not significant as solving times. 2 Although, they use some of the openly available precedence graphs, they have generated task times randomly.
Mitchell 21 Roszieg 25 Heskia 28 Buxey 29 Sawyer 30 Lutz1 32 Gunther 35 Kilbrid 45 Hahn 53 Warnecke 58 Tonge 70 Wee-mag 75 Arc83 83 P optimal solutions found for each problem group are listed with an aggregate on the last row. Although SI is not performing well (an optimal solution is found for 32 instances) as the problem specific implementation of [9] (67 instances), HIT finds almost the same number of optimal solutions (66 instances) and MAD finds more optimal solutions (72 instances) within the time limit. In this paper, we have encoded the SALBP-WS in ASP. This problem aims at balancing the workloads evenly among workstations in an assembly line. We have performed various experiments and they showcase better scalability results compared to problem specific SALBP-WS solvers.
The modular ASP encodings make it possible for us to try various criteria to quantify how balanced the SALBP assignment is. This issue is especially important for SALBP-WS solvers using problem specific search algorithms since they heavily depend on one optimization criterion (not just due to calculation of the optimization function, but also the need for theoretical bound analysis for improving solving performance) and supporting another one is not as easy as in the case of ASP.
Most of the recent related work on SALBP-WS rely on the SI criterion [10, 1, 9]. Our experiments show other criteria like M AD can also be used without significant deviation in assignment quality. This can even improve the computational performance of the system like in the case of our encodings.
Apart from criteria SI and M AD, we proposed a novel criterion based on idle times of workstations. Using the new HIT criterion, SALBP-WS problem can be modeled as a lexicographical multi-objective optimization problem. This new criterion can also be beneficial for other work related to ALBPs.
One important future line of research is to benefit from other SALBP-WS solvers that compute lower and upper bounds [1, 9] for the problem instance in ASP encodings.