# Modeling the Parallel Machine Scheduling Problem with Worker- and Position-Dependent Processing Times

Jairo Montoya-Torres, Valérie Botta-Genoulaz, Nick Materzok, Porgeir Páll Gíslason, Sélène Mendiela

## ► To cite this version:

Jairo Montoya-Torres, Valérie Botta-Genoulaz, Nick Materzok, Porgeir Páll Gíslason, Sélène Mendiela. Modeling the Parallel Machine Scheduling Problem with Worker- and Position-Dependent Processing Times. IFIP International Conference on Advances in Production Management Systems (APMS), Sep 2021, Nantes, France. pp.351-359, 10.1007/978-3-030-85906-0_39. hal-03523949

HAL Id: hal-03523949

https://hal.science/hal-03523949

Submitted on 20 Mar 2023

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_2.png" /></figure>

ifip

International Federation for Information Processing

This document is the original author manuscript of a paper submitted to an IFIP
conference proceedings or other IFIP publication by Springer Nature. As such, there
may be some differences in the official published version of the paper. Such
differences, if any, are usually due to reformatting during preparation for publication or
minor corrections made by the author(s) during final proofreading of the publication
manuscript.
# Modeling the Parallel Machine Scheduling Problem with
Worker- and Position-Dependent Processing Times

Jairo R. Montoya-Torres¹[0000-0002-6251-3667], Valérie Botta-Genoulaz²[0000-0003-2565-6690],
Nick Materzok², Þorgeir Páll Gíslason², and Sélène Mendiela²

¹ School of Engineering, Universidad de La Sabana, Chia, Colombia
jairo.montoya@unisabana.edu.co

² Univ Lyon, INSA Lyon, Université Claude Bernard Lyon 1, Univ Lumière Lyon 2, DISP,
EA4570, 69621 Villeurbanne, France
valerie.botta@insa-lyon.fr

**Abstract.** Traditional deterministic scheduling problems consider that processing times of jobs are fixed and constant over time. However, this assumption is not realistic in practice in hand-intensive manufacturing contexts. To deal with this, the current paper studies the deterioration effect of processing times on a parallel machine scheduling problem. In such a case, job processing times depend on the position of jobs in the execution sequence. The objective function is the minimization of the maximum delay of the set of jobs, that is the makespan. A mixed-integer linear programming model is provided for the basic case in which the processing time of jobs deteriorate only as a function of their position in the schedule. Then, two original extensions are proposed. The first one considers that both the position and the worker do impact the processing time, while in the second situation workers can have a break after a given period of time. Preliminary experiments are carried out to illustrate the impact of such situations on the objective function. Results are promising.

**Keywords:** Scheduling, Workers, Deterioration effect, Position-dependent Processing Times, Mathematical Modeling.

## 1 Introduction

Personnel scheduling in productive or service systems (e.g., hospitals, universities, call centers, banks, postal services, airlines and hand-intensive manufacturing industries) does require to make decisions in regard to the assignment of workers for the execution of a number of tasks during a time horizon. As pointed out in [1], this problem impacts on both the cost of operations and the service level to customers. In addition, some other physical or psychological issues can impact the actual performance of the schedule as well as moral, mental health and social welfare of workers [16,17].

In traditional scheduling models, human conditions of workers are ignored, and assumptions consider that he/she is a predictable agent in the system with perfect availability, deterministic processing times, and that fatigue or learning has no effects on
productivity [2]. These assumption does reduce the complexity and computational tractability of the problem. However, important characteristics of workers are neglected as a factor of variability in the productive system [2,11,16,18]. Under this context, this paper is motivated by the inclusion of particular work conditions, as the “deterioration effect”. Hence it deals with the problem of scheduling a set of jobs on a group of workers with homogeneous skills, where the productivity of workers deteriorates over time, and so the actual execution times of jobs are increased. According to the literature [8], this deterioration can be model either as a function of the position of jobs in the schedule or as a cumulative function of the time the execution of jobs started. Each approach has advantages and drawbacks. In any case, mathematical and computational complexity of the problem is increased. The introduction of a decrease in the productivity rate of workers during the scheduling horizon results in a more realistic representation of the system, especially in hand-intensive production, and support the construction of better decision-making models [8]. In the scheduling literature, the deterioration effect has been studied from two main approaches, either the processing times of a job increase depending on the waiting time until the start of its execution (starting time deterioration, or time-dependent processing times), or the processing times increase depending on the number of jobs previously scheduled until the beginning of the execution of a given job (position deterioration or sequence-dependent processing times) [13]. This paper considers the second approach since it has been less studied, even though this is the case of the decrease in the workers productivity due to physical exhaustion by repetitive work [10].

For the case of multiple parallel resources, Mosheiov [14] proposed to convert the position-dependent scheduling problem with linear deterioration of processing times to an assignment problem. The option of job rejection was considered in the works of [4]. Mosheiov [15] studied the minimization of the maximum workload. Huang & Wang [5] evaluated the minimization of the absolute deviation of both the completion time and the waiting time of jobs. Chen et al. [3] considered a deterioration function by parts to minimize the sum of completion times. Finally, Moreno-Camacho et al. [12], evaluated the performance of various mathematical models for makespan and tardiness minimization. All these works considered the same deterioration factor for all workers.

The problem under studied is an extension of the job scheduling problem in parallel resources with minimization of the makespan. This latter is known to be strongly NP-hard, even for the 2-machines case [7]. The case with simple linear deteriorating jobs is also proven to be NP-hard in strongly sense [6,9]. Although some works have studied scheduling with the deteriorating effect in processing times with identical parallel resources (i.e., workers), majority of those studies focus on the analysis of mathematical properties of the deteriorating effect. Scarcity of works propose solution procedures, except the work in [12], where the complexity (in terms of efficiency and capacity) of mixed-integer linear programming (MILP) models for makespan and tardiness minimization is deeply explored. The objective of this paper is to formally model, through an MILP approach, the parallel resources scheduling problem with position-dependent deteriorating processing times under two new original conditions: (i) considering worker-dependent deterioration rates, and (ii) breaks during the scheduling. The impact of these situations is analyzed using an illustrative example.
To this end, Section 2 formally describe the basic problem under study, as well as the variants considered. Section 3 presents the results of the computational experiment. Finally, the conclusions of the work and perspectives of future research are outlined in Section 4.

## 2 Problem description and mathematical modeling

We have a set of $n$ independent jobs $i=1,...,n$ and $m$ identical workers $j=1,...,m$ who can perform any of the $n$ jobs, under the same conditions. Each worker can only perform one job at a time and pre-emption is not allowed. For each job $i$, a baseline deterministic processing time $p_i$ is known in advance, representing the expected duration to execute the job without any deterioration and independent of the allocated worker. The special characteristic of the problem studied here is that the actual execution time of a job depends on the position in the sequence: processing times increase as a function of their positions in the schedule. That is, the actual processing time of job $i$ in the $k$-th position of the schedule is computed as $p_{ik} = p_i k^\alpha$, where $\alpha$ is the deterioration rate. This exponential deterioration rate follows the original proposition given in [11], where the factor $\alpha$ models the decrease in worker productivity.

A MILP model is first proposed for makespan minimization with a single position-dependent deterioration rate. Then, a first realistic extension of the model is presented to allow both position- and worker-dependent deterioration. The second extension consists in another realistic condition in which workers are allowed to have breaks during the production period.

### 2.1 Makespan minimization with position-dependent deterioration

The set of jobs is denoted as $N$, the set of identical workers is denoted as $M$, and the set of positions in the sequence is denoted as $R$, where $|R| = |N| - |M| + 1$. The parameters are the number $n = |N|$ of jobs, the number $m = |M|$ of available workers, the deterioration rate $\alpha$, with $0 \le \alpha \le 1$, and the processing time $p_{ik}$ of job $i \in N$ scheduled on position $k \in R$. The set of decision variables: $x_{jik} = 1$ if job $i \in N$ is executed by worker $j \in M$ at position $k \in R$ in the schedule, 0 otherwise; $C_{jk}$ is the completion time of the job executed by worker $j \in M$ at position $k \in R$; and $C_{max}$ is the makespan. The model reads as follows:

$$ \text{Min } C_{max} \tag{1} $$

Subject to:

$$ \sum_{j \in M} \sum_{k \in R} x_{jik} = 1 \qquad \forall i \in N \tag{2} $$

$$ \sum_{i \in N} x_{jik} \le 1 \qquad \forall j \in M, k \in R \tag{3} $$

$$ C_{j1} = \sum_{i \in N} p_{i1} x_{ji1} \qquad \forall j \in M \tag{4} $$
$$C_{jk} = C_{j,k-1} + \sum_{i \in N} p_{ik}x_{jik} \quad \forall j \in M, k \in R \setminus \{1\} \quad (5)$$

$$C_{max} \geq C_{j,(n-m+1)} \quad \forall j \in M, k \in R \quad (6)$$

$$x_{jik} \in \{0,1\} \quad \forall j \in M, i \in N, k \in R \quad (7)$$

In the above formulation, the objective function (1) minimizes the maximum completion time of all jobs (makespan). Constraints (2) and (3) ensure that one and only one job i is assigned to only one worker j in only one position k. Constraints (4) compute the completion time for the job scheduled in the first position to be executed by the worker j. Constraints (5) compute the completion time of the job in the k-th position of the worker j. Constraints (6) compute the value of decision variable $C_{max}$. Finally, the description of binary decision variables is given by Constraints (7).

## 2.2 Position- and worker-dependent deterioration

The previous basic model assumes that the processing time of jobs deteriorates equally for all workers at an identical rate; therefore all workers share the same deterioration factor $\alpha$. In real-life, however, the decrease of productivity can differ from one worker to another depending on their physical or psychological conditions. In consideration of this aspect, an extension can now be formulated where the parameter of the processing time changes from $p_{ik}$ to $p_{jik}$. Consequently, the processing time no longer dependents only on the position k in the schedule but on both the position k and the worker j that executes the respective job i. That is, the deteriorating factor becomes $\alpha_j$ for worker j. By integrating the worker-dependency in the deterioration factor and thus in the parameter of the processing time, the model can still be classified as a parallel machine scheduling problem with identical resources.

To formulate the problem as a MILP model, the new parameter for the actual processing time is defined as $p_{jik} = p_{i}k^{\alpha_{j}}$ for job i $\in N$ scheduled on position k $\in R$ while executed by worker j $\in M$. Constraints (4) and (5) are now rewritten as follows:

$$C_{j1} = \sum_{i \in N} p_{ji1}x_{ji1} \quad \forall j \in M \quad (4a)$$

$$C_{jk} = C_{j,k-1} + \sum_{i \in N} p_{jik}x_{jik} \quad \forall j \in M, k \in R \setminus \{1\} \quad (5b)$$

## 2.3 Position- and worker-dependent deterioration and breaks

Another extension that improves the practical applicability of the model is the implementation of breaks in the schedule. Breaks allow workers to rest and recharge to continue working. The underlying assumption of our model is that breaks lead to a decrease of the deterioration factor depending on the duration of the break, i.e. a recovery for the worker. Formally speaking, a break of duration $d_{break}$ takes place after a given position $k_{break}$ for every worker j. In a given schedule, the duration of breaks is fixed and identical for all workers. As a result, the deterioration factor decreases by the
following function: $a(k_{break} + 1) = a(k_{break}) - 0,1 * d_{break}$. In sections 2.1 and 2.2, the deterioration rate $\alpha$ has been considered to be constant which means that it is identical at any position $k$ in the schedule. By including breaks and assuming that the deterioration decreases but remains constant after the decrease, the following definition can be used, where $\alpha_0$ represents the deterioration rate at position $k = 0$. Figure 1a depicts an exemplary function for $\alpha_0 = 0,5$ and a break of $d_{break} = 2$ at position $k = 5$ which leads to a decreased deterioration factor of $a = 0,3$ after the break, computed as follows:

$$ \alpha(k) = \alpha_0 \qquad \forall k \le k_{break} \qquad (8) $$

$$ \alpha(k) = \alpha_0 - 0,1 * d_{break} \qquad \forall k > k_{break} \qquad (9) $$

<figure><img src="image_3.png" /><figcaption>a) Constant deterioration factor with break.</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>b) Increasing deterioration factor with break</figcaption></figure>

<caption>**Fig. 1.** Constant and increasing deterioration factor with break.</caption>

A second and more realistic way of modelling the deterioration rate is to include a general increase over the positions in the schedule. By that, it is considered that workers become less and less productive throughout the day. Assuming that the increase is also linear and breaks are still in place, the following definition can be used. Figure 1b shows an example of an increasing deterioration factor with a break, computed as follows:

$$ a(k) = 0,1 * (k - 1) + a_0 \qquad \forall k \le k_{break} \qquad (10) $$

$$ a(k) = 0,1 * (k - 1) + a_0 + a(k_{break}) - 0,1 * d_{break} \qquad \forall k > k_{break} \qquad (11) $$

## 3 Comparison between models

The basic MILP model and its extensions have been implemented to carry out an illustrative computational experiment. Models were coded on GAMS (General Algebraic Modeling System) and run on a PC with Windows 10, processor Intel® Core™ i5-
8250U at 1.6 GHz, and 8 GB of RAM. A set of 10 jobs and two workers are considered in this experiment, with baseline processing times being 8, 7, 5, 6, 7, 3, 2, 9, 10, and 2. Running times were about 16 minutes.

In a first instance, the behavior of the basic model is analyzed by looking into how different deterioration factors affect the scheduling. It is human nature to fatigue, but people usually do at different rates. This is represented by the different values of the deterioration factor, that was set from 0 to 1. Figure 2a depicts the solution obtained by the MILP model. For every deterioration factor, there are two bars, one for each worker, that show the assignment of jobs and their duration. The longest bar represents the makespan. As observed, when the deterioration factor is set to zero (i.e., workers never get fatigued), the makespan is the lowest; the makespan generally increases as the deterioration factor increases. Note that the solution schedules jobs in such a way that jobs with higher processing times are allocated at the beginning, while jobs with low processing time are at the end. That happens because the equation for deteriorated processing times leads to a higher absolute increase for jobs with high processing times. Since this increase would have a greater impact on the makespan, they get assigned to the beginning of the schedule where the deterioration is less strong.

<figure><img src="image_5.png" /><figcaption>**Fig. 2.** Two-workers schedule for (a) the basic scenario, and (b) worker-dependent deterioration.</figcaption></figure>

The second analysis was carried out on how the scheduling is performed if the workers would have different deterioration factors. Recall that this approach models the situation in which workers do not necessarily fatigue at the same rate. For this instance, the deterioration factors were set between 0 and 0.8 but never as the same number. Figure 2b shows the obtained assignment and makespan (the ordinate axis indicates the deterioration factors of the two workers). As per the results, in most cases the worker with the lower deterioration factor executes more jobs. In some cases, however, both workers perform an equal number of jobs but the worker with the lower deterioration factor gets assigned the jobs that have a higher baseline processing time. This is due to the same reason that jobs with high processing time are assigned earlier in the schedule,
that is, the solver tries to minimize the absolute increase of processing times by deteri-
oration as it would have an impact on the makespan. For example, looking at Figures
2a and 2b, in most of cases, having the same deterioration rate for both workers drives
to a worst performance than modeling independent deterioration. As a matter of fact,
the makespan is 42 time-units with both workers having $\alpha = 0.4$, while it decreases to
36 time-units with $\alpha_1 = 0$ and $\alpha_2 = 0.8$. This represents a decrease of 14.3% on the
makespan value.

The second extension includes the assumption of breaks that decrease the deteriora-
tion factor. In order to see the benefits, the model was run for different break durations
from 0 to 4 units of time. To compare the results, the respective break duration was
added to the total makespan. It is assumed that the deterioration factor is constant before
and after the break and that it begins with $\alpha_0 = 0.5$. The input data is the same as before.
Figure 3 shows the makespan for each break duration and visualizes the time of the
break by a white space between two consecutive jobs. Comparing the makespans for
the different break durations, it is observed that there is a trade-off which has to be
balanced. On the one hand, breaks decrease the deterioration factor which keeps the
processing times and thus the makespan lower. On the other hand, breaks increase the
makespan as they lead to idle-time in the schedule. Looking at the makespan, it shows
that the first effect of decreasing the deterioration factor becomes dominant with a
longer break duration. Until a break duration of 2, the makespan increases whereas it
decreases again for durations of 3 and 4. This consideration is quite relevant for the
planning of breaks in real life applications.

<figure><img src="image_6.png" /><figcaption>Fig. 3. Exemplary schedule of two workers with breaks.</figcaption></figure>

4 Conclusions and perspectives

This paper studied the problem of job scheduling in hand-intensive production systems.
Workers are considered with homogeneous skills, but their productivity decrease over
time according to a deterioration rate. A mixed-integer linear programming approach
was employed to model three situations. The former “all workers deteriorate at the same
rate”, already studied in the literature is the basic situation that serves as a reference to analyze two new original situations: (i) “each worker has his/her own deterioration rate”, and (ii) the latter coupled with “the impact of breaks for worker recovery”. The first experiments allow us to see the interest of individualizing the deterioration rate per worker (by comparison with a global average rate), and also to identify the duration of breaks as a lever for optimization.

Since this is one of the few works in the literature addressing these problems, several lines for future research are open. For instance, behavior of workers is also impacted (not necessarily in the same ratio) by learning effects. One line for further research can focus on the simultaneous evaluation of deterioration rates and recovery curves, in addition to include breaks during the scheduling horizon. Also, non-linear deterioration or recovery functions can be considered, as well as stochastic modeling. Heterogenous labor or worker preferences are also characteristics to be included. Other lines for future research include the possibility to extend the study to other non-classical optimization criteria such as maximization of machines exploitation time, workload balance among workers, tardiness, etc. Finally, because of its computational complexity, the use of heuristics and/or meta-heuristics can be a promising line for future research in order to solve large-scale versions of the problem.

## References

1. Alfares, H.K.: Survey, Categorization, and Comparison of Recent Tour Scheduling Literature. Annals of Operations Research, 127(1-4), 145-175 (2004).

2. Boudreau, J. W., Hopp, W., Mcclain, J.O., Thomas, L.J.: On the interface between operations and human resources management. Manufacturing & Service Operations Management, 5(3), 179-202 (2003).

3. Chen, W., Guo, P., Zhang, Z., Zeng, M., Liang, J.: Variable Neighborhood Search for Parallel Machines Scheduling Problem with Step Deteriorating Jobs. Mathematical Problems in Engineering, 2012, Article ID 928312.

4. Gerstl, E., & Mosheiov, G.: Scheduling on parallel identical machines with job-rejection and position-dependent processing times. Information Processing Letters, 112(19), 743-747 (2012).

5. Huang, X., Wang, M.-Z.: Parallel identical machines scheduling with deteriorating jobs and total absolute differences penalties. Applied Mathematical Modelling, 35(3), 1349-1353 (2011).

6. Ji, M., Cheng, T.C.: Parallel-machine scheduling of simple linear deteriorating jobs. Theoretical Computer Science, 410 (38-40), 3761-3768 (2009).

7. Lawer, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B.: Sequencing and scheduling: algorithms and complexity. Centre for Mathematics and Computer Science Report BS-R8909, Stichting Mathematisch Centrum, Amsterdam, Holland (1989).

8. Lodree, E. J., Geiger, C. D., Jiang, X.: Taxonomy for integrating scheduling theory and human factors: Review and research opportunities. International Journal of Industrial Ergonomics, 39(1), 39-51 (2009).

9. Miao, C., Zou, J.: Parallel-Machine Scheduling with Time-Dependent and Machine Availability Constraints. Mathematical Problems in Engineering, 2015, Article ID 956158 (2015).

10. Montoya-Torres, J.R., Sánchez, S., Moreno-Camacho, C.: A literature-based assessment of human factors in shop scheduling problems. IFAC-PapersOnLine, 52(10), 49-54 (2019).
11. Moreno-Camacho, C. A., & Montoya-Torres, J. R.: Workforce scheduling with social re-sponsibility considerations. In Proceedings of the 4th IEEE International Conference on Advanced Logistics and Transport (ICALT) (pp. 24–29). IEEE Publishing (2015).

12. Moreno-Camacho, C.A., Montoya-Torres, J.R., Vélez-Gallego, M.C.: A Comparison of Mixed-Integer Linear Programming Models for Workforce Scheduling with Position-dependent Processing Times. Engineering Optimization, 50(6), 917-932 (2018).

13. Mosheiov, G.: A note on scheduling deteriorating jobs. Mathematical and Computer Modelling, 41(8-9), 883–886 (2005).

14. Mosheiov, G.: Minimizing total absolute deviation of job completion times: extensions to position-dependent processing times and parallel identical machines. Journal of the Operational Research Society, 59, 1422-1424 (2008).

15. Mosheiov, G.: A note: Multi-machine scheduling with general position-based deterioration to minimize total load. International Journal of Production Economics, 135(1), 523–525 (2012).

16. Petrovic, S., Vanden Berghe, G.: A comparison of two approaches to nurse rostering problems. Annals of Operations Research, 194(1), 365–384 (2012).

17. Puente, J., Gómez, A., Fernández, I., Priore, P.: Medical doctor rostering problem in a hospital emergency department by means of genetic algorithms. Computers & Industrial Engineering, 56(4), 1232–1242 (2009).

18. Thompson, G. M., Goodale, J.C.: Variable employee productivity in workforce scheduling. European Journal of Operational Research, 170(2), 376–390 (2006).