<figure><img src="image_1.png" /></figure>

HAL
open science

# A DRC Scheduling for Social Sustainability: Trade-Off Between Tardiness and Workload Balance

Muhammad Akbar, Takashi Irohara

► To cite this version:

Muhammad Akbar, Takashi Irohara. A DRC Scheduling for Social Sustainability: Trade-Off Between Tardiness and Workload Balance. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2019, Austin, TX, United States. pp.206-213, 10.1007/978-3-030-30000-5_27. hal-02419261

HAL Id: hal-02419261

https://inria.hal.science/hal-02419261

Submitted on 19 Dec 2019

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# A DRC Scheduling for Social Sustainability: Trade-off between Tardiness and Workload Balance

Muhammad Akbar<sup>1,2[0000-0001-5736-4313]</sup> and
Takashi Irohara<sup>1[0000-0003-2040-9703]</sup>

**Abstract.** A dual resource constrained (DRC) with fewer operators who could control parallel semi-automatic simultaneously potentially faces the unbalance workload problem that is related to social topics in Global Reporting Initiative Sustainability Reporting Standards (GRI Standards). Balancing the operator workload, on the other hand, could change the schedule structure resulting in some additional delay. This proposed study develops a multi-objective mixed integer non-linear programming (MINLP) with total tardiness and workload smoothness index (WSI) as the objective functions to measure the delay and workload balance respectively. To solve the model, a well-known non-dominated sorting genetic algorithm II (NSGA-II) is used to yield the non-dominated solutions showing the alternative schedule options. The results show that the effort in balancing the workload could raise the lateness. The important finding is that WSI can be improved significantly in the small proportion on the most left side of the total tardiness range.

**Keywords:** DRC scheduling · Social · Total tardiness · WSI · NSGA-II

## 1 Introduction

Dual resource constrained (DRC) scheduling allows the operators to move between workstations to perform a task [1]. This scheduling matches as a strategy for manufacturers equipped by semi-automatic machines in which the operators can move while the machining time. Although this strategy could increase labor productivity, an inappropriate schedule will cause large tardiness [2]. Also, it could generate workload unbalance causing jealousy feeling between operators.

Many studies in DRC scheduling that deals with fewer operator allow their moving between machine but only supervising one job at the time [3, 4]. In contrast, DRC scheduling which considers simultaneous supervision that may cause the increment of the execution time is still rare [5]. A study manage operators to move between workstations to perform setup activity with zero moving time [6]. Then, a recent research extends it by considering two activity assignment (setup

<footnote n="1">¹ Sophia University, 7-1 Kioi-Cho, Chiyoda-Ku, Tokyo 102-8554, Japan
muhammad@eagle.sophia.ac.jp, irohara@sophia.ac.jp</footnote>

<footnote n="2">² Bandung Institute of Technology, Jl. Ganesha No. 10, Bandung 40132, Indonesia
muhammad@itb.ac.id</footnote>
and unloading) and the transport time between machines [7]. Both studies have
the same objective function which is to minimize the makespan. However, this
proposed research considers the total tardiness instead.

DRC scheduling problem that includes a social indicator as an additional ob-
jective function is very few even for all scheduling problem type [8]. Two recent
papers analyze the trade-off relations of tardiness-operator productivity [2] and
makespan-workload balance [9]. To extend those, this proposed research investi-
gates the impact of workload balance on total tardiness. Because the scheduling
problem is still new, this study is the first one in analyzing the relation. Global
Reporting Initiative Sustainability Reporting Standards (GRI Standards) con-
firms that treating people unequally by imposing unequal burden is discrimina-
tion that belongs to the social dimension [10]. Therefore, this study hopefully
could generate a better schedule but also to contribute for sustainable manufac-
turing development. Besides, this study also proposes a metaheuristic technique,
which is an adjusted non-dominated sorting genetic algorithm II (NSGA-II) [11].

## 2 Problem Formulation

The objective of this study is to analyze the impact of the workload balance as an additional objective function when attached to the basic single-objective DRC model in an identical parallel machine environment [2]. The production system consists of a set $I = (i_1, i_2, ..., i_m)$ of $m$ semi-automatic machines with a set $K = (k_1, k_2, ..., k_w)$ of $w$ operators, where $w < m$, to execute a set $J = (j_1, j_2, ..., j_n)$ of $n$ jobs. For the modeling purpose, a set $J' = (j_0, j_1, j_2, ..., j_n)$, which includes a dummy job $j_0$, also exists to assist the precedence constraint.

Each job through setup, machining, and unloading processes in one machine.
Operators can only contribute to setup and unloading activities in a set $A =
(a_s, a_u)$ of tasks, and they could go to another machine after finishing a task.
The duration time to perform task $b$ of job $l$ is $o_{bl}$. Then, the machining time of
job $l$ is $p_l$. Finally, $m_{hi}$ represents the operator moving time between machine $h$
and machine $i$. Another parameter is a big number $B$ needed in the modeling.

There are two objective functions in the model formulation, namely, total tardiness and operator's workload smoothness index (WSI) [9] as shown in equation 1 and 2 respectively. A schedule with smaller WSI has better workload balance. And it becomes a perfect balance if the WSI equal to 0. Since the WSI is non-linear, the model becomes a mixed integer non-linear programming (MINLP). The following mathematical model shows the decision variables and problem formulation. Please note that the $x$ variable accommodates two types of precedence relation, i.e., task order performed by each operator and job sequence assigned to each machine. Therefore, this variable needs seven suffixes to indicate those.

Decision Variables

$x_{khajibl}$ : a binary variable that equal to 1 if operator $k$ performs task $b$ of job $l$ in machine $i$ after finishing task $a$ of job $j$ in machine $h$

$o_{bl}^c$ : the completion time of task $b$ of job $l$
$p_{bl}^c$ : the machining completion time of task b of job l

$m_{bl}^c$ : the operator moving completion time to perform task b of job l

$t_l$ : the tardiness of job l

$nw_k$ : the total non-waiting time of operator k

$nw_{max}$ : the maximum total non-waiting from all operators

$q_{fl}$ : a binary variable that equal to 1 if setup of job l starts before unloading job f on the same machine

Model

$$ \text{minimize } f_1 = \sum_{l \in J} t_l \qquad (1) $$

$$ \text{minimize } f_2 = WSI = \sqrt{\sum_{k \in K} (nw_k - nw_{max})^2} \qquad (2) $$

$$ \sum_{k \in K} \sum_{h \in I} \sum_{a \in A} \sum_{j \in J'} \sum_{i \in I} x_{khajibl} = 1 \quad \forall b \in A; l \in J \qquad (3) $$

$$ \sum_{k \in K} \sum_{h \in I} \sum_{i \in I} \sum_{b \in A} \sum_{l \in J} x_{khajibl} \le 1 \quad \forall a \in A; j \in J \qquad (4) $$

$$ \sum_{h \in I} \sum_{i \in I} \sum_{b \in A} \sum_{l \in J} x_{kha_{uj0ibl}} \le 1 \quad \forall k \in K \qquad (5) $$

$$ \sum_{h \in I} \sum_{i \in I} \sum_{b \in A} \sum_{l \in J} x_{kha_{sj0ibl}} = 0 \qquad (6) $$

$$ \sum_{k \in K} \sum_{h \in I} \sum_{a \in A} \sum_{j \in J'} x_{khajia_{sl}} - \sum_{q \in K} \sum_{g \in I} \sum_{c \in A} \sum_{f \in J'} x_{qgcfia_{ul}} = 0 \quad \forall i \in I; l \in J \qquad (7) $$

$$ \sum_{h \in I} \sum_{a \in A} \sum_{j \in J'} x_{khajibl} \ge \sum_{g \in I} \sum_{c \in A} \sum_{f \in J} x_{kiblgcf} \quad \forall k \in K; i \in I; b \in A; l \in J \qquad (8) $$

$$ o_{bl}^c - m_{bl}^c \ge o_{bl} \quad \forall b \in A; l \in J \qquad (9) $$

$$ m_{bl}^c - o_{al}^c \ge \sum_{h \in I} \sum_{i \in I} \sum_{k \in K} m_{hi} \times x_{khajibl} - B \times (1 - \sum_{h \in I} \sum_{i \in I} \sum_{k \in K} x_{khajibl}) \quad \forall b \in A; l \in J; a \in A; j \in J' \qquad (10) $$

$$ o_{a_0 l}^c - p_l^c \ge o_{a_0 l} \quad \forall l \in J \qquad (11) $$

$$ p_l^c - o_{a_0 l}^c = p_l \quad \forall l \in J \qquad (12) $$
$$
\left\{
\begin{array}{l}
o_{a_s l}^c - o_{a_u f}^c \ge \sum_{k \in K} \sum_{h \in I} \sum_{a \in A} \sum_{j \in J'} o_{a_s l} \times x_{khajia_s l} \\
-B \times \left(2 - \sum_{k \in K} \sum_{h \in I} \sum_{a \in A} \sum_{j \in J'} (x_{khajia_s l} + x_{khajia_s f}) + q_{fl}\right) \\
\qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \forall i \in I; f \in J; l > f \\
\\
o_{a_s f}^c - o_{a_u l}^c \ge \sum_{k \in K} \sum_{h \in I} \sum_{a \in A} \sum_{j \in J'} o_{a_s f} \times x_{khajia_s f} \\
-B \times \left(2 - \sum_{k \in K} \sum_{h \in I} \sum_{a \in A} \sum_{j \in J'} (x_{khajia_s l} + x_{khajia_s f}) + 1 - q_{fl}\right)
\end{array}
\right.
\qquad (13)
$$

$$
\begin{array}{l}
o_{a_u j_0}^c = 0 \qquad (14) \\
t_l \ge o_{a_u l}^c - d_l \quad \forall l \in J \qquad (15)
\end{array}
$$

$$
t_l \ge o_{a_u l}^c - d_l \quad \forall l \in J \qquad (15)
$$

$$
t_l \ge 0 \quad \forall l \in J \qquad (16)
$$

$$
nw_k = \sum_{h \in I} \sum_{a \in A} \sum_{j \in J'} \sum_{i \in I} \sum_{b \in A} \sum_{l \in J} x_{khajibl} \times (o_{bl} + m_{hi}) \quad \forall k \in K \quad (17)
$$

$$
nw_{max} \geq nw_k \quad \forall k \in K \qquad (18)
$$

$$
x_{khajibl} \in \{0;1\} \quad \forall k \in K; h \in I; a \in A; j \in J'; i \in I; b \in A; l \in J \quad (19)
$$

$$
q_{fl} \in \{0;1\} \quad \forall f \in J; l > f \qquad (20)
$$

Constraints 3 and 4 force each task of jobs is dedicated only to a unique
machine and operator. Those also keep each task having only one predecessor and
at most one successor task. Constraints 5 and 6 ensure that only unloading task is
performed as the first task of each operator for job j₀. Constraint 7 forces each job
only utilizes one machine. Then, equation 8 sets the tasks precedence constraint
performed by each operator. Equation 9 and 10 define the relation between
moving activity and the tasks done by operator. Meanwhile, equations 11 and
12 connect the machining activity to the tasks on each machine. The twofold
equation 13 sets the jobs precedence constraint on each machine. Equation 14
ensures that the unloading time of j₀ is zero. Then, equation 15 and 16 set each
job tardiness value. Equation 17 computes each operator non-waiting time and
equation 18 stores its maximum value used to compute the WSI. Finally, the
rest of the equations 19 and 20 are the binary constraints.

3 The Metaheuristic Methods

This study uses the famous NSGA-II [11] to solve the multi-objective MINLP.
Some adjustments needed in this scheduling problem are the encoding scheme
representing the solution space and the decoding scheme translating the code
becoming objective values. The proposed NSGA-II applies a single chromosome
which is used in the previous research [7]. The chromosome represents the jobs
sequence when evaluated in the decoding scheme. The chromosome decoding
<figure><img src="image_3.png" /><figcaption>Fig. 1. An example of a chromosome conversion</figcaption></figure>

procedure yields the scheduling solution and its objective functions as described in Algorithm 1. In detail, Fig. 1 illustrates how the decoding procedure works for chromosome 4-2-1-3 in case with 4 jobs, 3 machines, and 2 operators. It also shows the complexity of the DRC scheduling problem where the Gantt chart must include the operator assignment to describe the schedule. The developed NSGA-II uses the binary tournament, two-point crossover [7], and block swapping schemes [13] for generating the offspring on each iteration. The binary tournament selects the chromosome based on the non-domination rank for the initial iteration and the crowded-comparison operator on the following iterations.

**Algorithm 1** Pseudocode for the Decoding Procedure

**INPUT:** A chromosome containing job sequence information

**OUTPUT:** The schedule with the total tardiness and WSI values.

1: **while** the number of allocated task smaller than 2n **do**

2:     assign one machine that could start the earliest;

3:     assign one operator that could start operating the selected machine the earliest

4:     **if** the previous task on the machine is **setup** **then**

5:         allocate unloading task for the same job of previous task

6:     **else** allocate **setup** task for a job picked from unassigned gene of the chromosome

7:     update the schedule

## 4 Numerical Examples and Results

This study codes the NSGA-II using Python® programming language run on 16-GB RAM PC powered by an octa-core 3.6-GHz processor. There are 16 cases
from three different problem sizes, namely, small, medium, and large as grouped on [7] which is identified by $n \times m \times w$ (jobs number $\times$ machines number $\times$ operators number). The time parameters come from uniform distribution, which are U[1, 79], U[1,99], U[1, 20], and U[3,10] respectively for setup, machining, unloading, and moving. Besides, the due dates dataset also comes from the uniform distribution, i.e., U[$Q(1 - T - R/2), Q(1 - T + R/2)$] as used in [12]. $Q$ is computed using equation 21, $T$ is the mean tardiness factor and $R$ is the relative range of the due dates. This experiment chooses $T = 0.8$ and $R = 0.4$ for generating very tight due dates dataset. NSGA-II uses trial-and-error to find the appropriate parameters, which are generation number, population size, crossover probability, and mutation probability until it reaches the same or lower tardiness value compared to the results of single-objective MILP as in [2].

$$Q = \frac{\sum_{l \in J} o_{as,l} + p_l + o_{a,u,l}}{m^2} \quad (21)$$

Figure 2 shows non-dominated set results for 16 selected cases from each problem size. It confirms that reducing the WSI will cause the increasing of total tardiness. In the small-sized problem instances, the non-dominated solutions, which few in number, approach straight line form. However, the solution points approach curve form separating solution in two groups when the problem becomes more complicated. The first part is located on the small proportion of the most left near the minimum value of total tardiness in which the WSI decreases significantly. This range is the most important thing if a manufacturer wants to increase the workload balance sacrificing only a small delay. Meanwhile, the second part that comes after the first range distributes the points near a line with a small gradient. It means that the total tardiness changes significantly while the WSI does not. Most non-dominated solutions flock in the first part for the large-sized instances, but they assemble in the second part for the medium-sized ones. Therefore, this study could assist the manufacturer to find the appropriate scheduling with better WSI if the small addition of the tardiness is tolerable.

## 5 Conclusions

This proposed study extends the previous studies on scheduling for social sustainability. It develops a multi-objective MINLP model of a complex DRC scheduling problem to minimize the total tardiness and WSI. The objectives pair, as far as known, has not been considered together on the previous multi-objective sustainable scheduling problems. The DRC scheduling is also relatively new problem in which fewer operators could perform setup or unloading tasks and they could move between machines in the machining time. This study adopts the famous NSGA-II in generating the non-dominated solutions. The results show that the effort to increase the workload balance will raise the total tardiness. The important finding is that WSI can be improved significantly in the small proportion on the most left side of the total tardiness range. For future research, it suggests to apply other better metaheuristic methods that suits to this DRC problem by performing comparative study.
<figure><img src="image_4.png" /></figure>

<caption>Fig. 2. Non-dominated set of the NSGA-II results for selected cases</caption>

<footnote>* Parameter setting for each problem: generation number – 10 (S), 100 (M), 250 (L); population size – 20 (S), 200 (M), 350 (L); crossover rate – 0.5 (S), 0.8 (M), 0.9 (L); mutation rate – 0.1(S), 0.2(M, L)</footnote>
Acknowledgment

We are thankful to the Hitachi Global Foundation for the scholarship support.

References

1. Xu, J., Xu, X., and Xie, S.Q.: Recent developments in Dual Resource Constrained (DRC) system research. European Journal of Operational Research **215**, 309–318 (2011)

2. Akbar, M. and Irohara, T.: A social-conscious scheduling model of dual resources constrained identical parallel machine to minimize tardiness and maximize operator productivity. In: Proceedings of International Conference on Computers and Industrial Engineering, CIE, **2018-December**, (2018)

3. Agnetis, A., Flamini, M., Nicosia, G., and Pacifici, A.: A job-shop problem with one additional resource type. Journal of Scheduling **14**, 225–237 (2011)

4. Paksi, A. B. N. and Ma'ruf, A.: Flexible job-shop scheduling with dual-resource constraints to minimize tardiness using genetic algorithm. In: IOP Conference Series: Materials Science and Engineering, vol. 114 p. 012060, Yogyakarta (2016)

5. Baptiste, P., Rebaine, D., and Zouba, M.: FPTAS for the two identical parallel machine problem with a single operator under the free changing mode. European Journal of Operational Research **256**, 55–61 (2017)

6. Costa, A., Cappadonna, F. A., and Fichera, S.: A hybrid genetic algorithm for job sequencing and worker allocation in parallel unrelated machines with sequence-dependent setup times. International Journal of Advance Manufacturing Technology **69**, 2799–2817 (2013)

7. Akbar, M. and Irohara, T.: Dual Resource Constrained Scheduling Considering Operator Working Modes and Moving in Identical Parallel Machines Using a Permutation-Based Genetic Algorithm. In: Moon I., Lee G., Park J., Kiritsis D., von Cieminski G. (eds) Advances in Production Management Systems. Production Management for Data-Driven, Intelligent, Collaborative, and Sustainable Manufacturing. APMS 2018. IFIP Advances in Information and Communication Technology, **535**, 464–472. Springer, Cham (2018).

8. Akbar, M. and Irohara, T.: Scheduling for Sustainable Manufacturing: A Review. Journal of Cleaner Production **205**, 866–883 (2018)

9. Akbar, M. and Irohara, T.: A social-conscious scheduling model of dual resources constrained identical parallel machine to minimize makespan and operator workload balance. In: Proceedings of the Asia Pacific Industrial Engineering & Management System Conference 2018, APIEMS, (2018)

10. GRI (Global Reporting Initiative) Sustainability Reporting Standards – Non-Discrimination (GRI 406), https://www.globalreporting.org/standards/gri-standards-download-center/. Last accessed 28 March 2019

11. Deb, K., Pratap, A., Agarwal, S., and Meyarivan, T.: A Fast and Elitist Multiobjective Genetic Algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation **6**(2), 182–195 (2002)

12. Lin, Y. K., Hsieh, H. T., and Hsieh, F. Y.: Unrelated Parallel Machines Scheduling Problem Using an Ant Colony Optimization Approach. International Journal of Industrial and Manufacturing Engineering **6**(8), 1727–1732(2012)

13. Costa, A., Cappadonna, F. A., and Fichera, S.: A hybrid genetic algorithm for minimizing makespan in a flow-shop sequence-dependent group scheduling problem. Journal of Intelligence Manufacturing **28**, 1269–1283 (2017)