An MILP model for workload fairness and incompatibility in seafaring staff scheduling problem

Abstract

Purpose

This paper treats the problem of scheduling seafaring staff inspired from a real case study, where the shipowner operates several vessel categories that require specific skills aiming to achieve a fair workload distribution and minimizing incompatibility between workers while meeting legal constraints, including requirements for days off and rest intervals between shifts.

Design/methodology/approach

A mixed integer linear problem (MILP) formulation has been built to address the seafaring staff scheduling problem by integrating multiple objectives and constraints. The model’s performance is tested through experimental results across varying parameter adjustments.

Findings

Our model was tested and validated using the XPRESS solver, and the results demonstrate its effectiveness in meeting the specified objectives and constraints. Notably, findings reveal that increasing the number of qualified workers leads to improved gains, until a certain threshold. Additionally, expanding the size of the workforce can result in longer execution times, specifically when incompatibility increases.

Originality/value

The originality of this study lies in proposing a generic novel model that deals with maritime staff scheduling, incorporating worker incompatibilities and workload fairness as key objectives.

Citation

Ben Moallem, M., Tighazoui, A., Houssin, R., Ammar, M.H., Dhouib, D. and Coulibaly, A. (2024), "An MILP model for workload fairness and incompatibility in seafaring staff scheduling problem", Maritime Business Review, Vol. ahead-of-print No. ahead-of-print. https://doi.org/10.1108/MABR-06-2024-0050

1. Introduction

The cost, more affordable than rail, road or air freight, plays a crucial role in sustainable development. Sea transport handles the majority of world trade; in terms of value, approximately 70% of cargo is managed by the global seaborne container trade (Weerasinghe et al., 2023). However, a handling terminal is a highly complex system where operations are handled within a 24-h cycle, demanding extensive equipment and manpower. Workers and their schedule are crucial for businesses including shipping companies aiming at matching every staff member to his ideal role at the right time while keeping operations running smoothly day-to-day. Staff Scheduling (SS) traditionally involves manual formulation, but the increasing complexity of such problems has made manual scheduling time-consuming and labor-intensive (Topaloglu, 2009). The complexity arises from various constraints and objectives that aim to meet a real-world challenge.

In this study, we investigate a real problem inspired by the maritime sector in Tunisia. The insights for our model development were gleaned through Semi-Structured Interviews (SSIs) conducted with the shipowner, as documented by (Ben Moallem et al., 2023). During these interviews, the shipowner expressed that legal constraints must be adhered to. This involves fulfilling certain obligations, such as providing a day of rest following a stretch of consecutive workdays and specifying a minimum rest period between shifts. Beyond legal constraints, the shipowner emphasized additional factors in optimizing SS, including the consideration of skills required for various types of ship - owners. Bucak et al. (2023) underscored the vital importance of qualified personnel in ports, highlighting that ports operate within a complex and constantly evolving dynamic environment. Furthermore, findings from the SSIs revealed that a fair distribution of workload is essential for ensuring satisfied workers and maintaining balanced salary bonuses.

In our maritime case study, workers are assigned individually to shifts, with each shift representing a trip dedicated to transporting passengers and vehicles. Since multiple workers are assigned to each trip, teamwork becomes essential. The shipowner emphasizes the importance of fostering good relationships among staff members to avoid conflicts and ensure smooth operations. As a result, there’s a focus on minimizing potential incompatibilities within the team to maintain a positive and efficient dynamic throughout the trip.

In this paper, we investigate how these objectives and constraints have been addressed in the existing literature, drawing from previous studies that have tackled similar issues. The paper is structured as follows: Section 2 provides a detailed literature review, while Section 3 outlines the scientific problem. Section 4 presents our proposed mathematical model, and Section 5 discusses the experimental results, including model validation and sensitivity analysis, before concluding.

2. Literature review

Since our research is focused on meeting shipowner challenges, we conducted an extensive review of studies related to the SS topic in the maritime field. However, we found only a few recent works, and these typically fail to integrate all the necessary objectives and constraints into a single model. In particular, none addresses the concept of incompatibility. The gaps in the literature and the challenges faced by our shipowner emphasize the need to broaden our scope to other fields.

Through a comprehensive literature review, we identified studies addressing various problems with differing objectives and constraints, including those of shipowners, and how other research has managed these challenges.

In SS-related issues, legal constraints are particularly critical, as compliance with regulations is essential. These constraints, such as maximum working hours, mandatory rest periods and required days off after consecutive workdays, are standard to ensure adherence to legal requirements. In the healthcare sector (Volland et al., 2017), proposed a model optimizing physician staffing with flexible shifts, considering labor agreements like weekly hours, shift lengths and rest periods. Recent studies by Ceschia et al. (2023), Amindoust et al. (2021), Armas et al. (2016), El Adoly et al. (2018) also address similar constraints. In public transport, Kang et al. (2019) scheduled drivers around mealtime, and Khmeleva et al. (2014) tackled rail freight crew scheduling within legal hours. In the airline context, Quesnel et al. (2019) introduced schedules adhering to rules like a minimum of 10 days off and a maximum of 6 consecutive workdays. In their 2021 study on the maritime sector, Lorenzo-Espejo et al. analyzed the labor regulations governing pilots' work schedules, including restrictions on consecutive workdays and the requirement for a minimum number of off-duty days. Similarly, in 2018, Leggate et al., conducted a study modeling crew scheduling for offshore supply vessels, where shipowners must comply with regulations dictating maximum work durations, minimum rest periods and limits on consecutive workdays for each crew member.

SS today’s consideration has grown towards other issues such as skills or qualifications. When some tasks require a particular skill, the personnel are considered from a heterogeneous group of employees, each with a particular set of skills. In some fields, skills are acquired through internships with specific hours, aiming to equip individuals with the necessary capabilities. This approach is seen in healthcare for medical training (Brech et al., 2019) and in the transport sector where workers gain skills through additional hours supervised by seniors (Akyurt et al., 2021; Kasirzadeh et al., 2015). In the maritime sector, a hierarchical skill structure is often observed, where operators are paid based on their primary task, even if they are assigned to lower-level duties and restricted from performing higher-level tasks (Francesco et al., 2014; Massimo et al., 2016). Industries typically rely on workers having pre-existing technical skills, with expertise gained through practical, hands-on experience on the job (Frihat et al., 2022; Campos Ciro et al., 2016; Othman et al., 2012; Pereira et al., 2021).

Recently, SS has been involved significantly and organizations have been based on the small-action-big-effect concept. This approach maximizes profitability by optimizing the efficient use of workers, ultimately contributing to their satisfaction. Managers can increase employees’ satisfaction by adapting issues such as preferred holidays, days off and rest periods. Works by Mohammadian et al. (2019) and El Adoly et al. (2018) explored scheduling models considering nurse day-off/shift preferences, while in the airline sector, schedules are tailored to staff member preferences for destinations and flight legs, as seen in studies like Quesnel et al. (2019). For other works dealing with worker preferences, the reader may refer to Armas et al. (2016), Kasirzadeh et al. (2015) and Chutima and Arayikanon (2020). In SS problems, worker preferences can shape the model either as optimization goals or constraints. Generally, when preferences are treated as objectives, they are often considered as “soft constraints,” allowing for flexibility in optimization and enabling trade-offs with other objectives such as cost minimization or operational efficiency. Expressing preferences can indeed include the ability to choose the colleagues with whom they prefer to work based on mutual affinity. This refers to the incompatibility minimization.

Incompatibility minimization: The aim of this objective is to reduce conflicts or incompatibilities between different workers within a schedule. Di Martinelly and Meskens (2017) emphasized the importance of maximizing affinities between surgical team members while minimizing idle time. Maheut et al. (2023) introduced a novel mixed-integer linear model for scheduling workers in sheltered employment centers. Their model incorporates skills and affinity matrices among workers, offering decision support in this intricate environment. Monteiro et al., (2015) proposed a mixed integer linear problem (MILP) model considering constraints that include priority of operations, affinities between surgical team members, renewable and non-renewable resources, various sizes of operating rooms and surgical team’s preferences/availabilities. Exploring incompatibility minimization in SS is essential for a harmonious work environment. Expressing a preference for selecting team members to minimize incompatibility is crucial for ensuring worker satisfaction. However, fair workload remains also important criterion for worker fulfillment.

Maximizing workload fairness: One of the most important factors of job satisfaction is salary and benefits derived from a fair workload distribution. The concept of equal workload distribution leading to similar salaries between workers is rooted in the idea of fairness and equity. When workers are assigned a similar number and type of tasks, it is reasonable to expect that they should receive similar salaries. However, fairness can be influenced by various factors, such as when tasks belong to different categories that are not uniformly rewarded. In such cases, it is crucial to ensure fairness across all shift categories. Additionally, some tasks may require specific skills, higher qualifications, or senior expertise, which must also be considered when determining compensation.

Workload fairness aims to guarantee that employees receive uniform bonuses, emphasizing the importance of salary and benefits in promoting job satisfaction. This objective is integrated in Achmad et al. (2021), where the objective function is formulated to minimize the violation of the constraints and balance nurse workload as a fairness criterion; their research aligns with Aktunc and Tekin (2018), who have solved a goal programming model to produce an optimal nurse schedule which provides fair workload and satisfies shift preferences of nurses. Lorenzo-Espejo et al. (2021) have focused on scheduling balanced in-port days among seafaring pilots and emphasizing consecutive rest days for extended breaks. In the same context, Ammar et al. (2013) identified fairness as a crucial factor in maritime personnel teams, demonstrating that distributing workload equally leads to salary fairness, as shifts are not compensated equally. Building on this concept, Koubaa et al. (2016) and Koubaa et al. (2022) employed alternative metaheuristics to optimize the same model, achieving better results than the approach proposed by Ammar et al. (2013).

Despite the large number of articles studied in SS, few have considered the dual objective of workload fairness coupled with incompatibility minimization. While previous studies such as Blochliger (2004) have highlighted similar concepts using mathematical models, they pointed out that solving this problem should be approached using heuristics, without implementing them.

A key innovation of this work is the introduction of incompatibility minimization as a novel objective function within the maritime field. Furthermore, workload fairness is added as a second objective, and we assess the combined objectives’ impact on decision-making and meeting a real-world challenge inspired by a shipowner.

In addition to legal constraints and consideration of workers' qualifications, according to our literature review, this case study has not yet been addressed in the literature and could contribute to operational research. It is also of interest to decision-makers in the maritime planning domain. The main contributions are as follows:

• (1)

  Optimizing a worker scheduling calendar in the maritime domain to minimize incompatibility between workers and ensure fairness through the equitable distribution of shift categories among employees, given that these categories are not similarly rewarded.

• (2)

  Considering and studying workers' qualifications and the percentage of gains they can bring to objectives.

• (3)

  Highlighting the limitations of MILP models in solving this type of problem across various randomly generated instances.

The literature review presented provides a foundation for understanding of the SS problem. The subsequent sections explore specific scheduling challenges faced by shipowners.

3. Problem description

To better present our issue, Figure 1 illustrates a schematic representation outlining the fundamental aspects of our model and its structure. It is important to emphasize that in our model, shifts are predetermined, and our objective revolves around efficiently assigning workers to their respective shifts. This assignment process considers various constraints and two objectives.

The SS problem involves the allocation of a specific number of workers W to a set of shifts J of categories L in days I. w = {1, …, W}, j = {1, …, J}, l = {1, …, L}, and i = {1, …, I} are, respectively, the index of worker, shift, category and day. The shipowner requires round-the-clock operations and therefore needs workers to cover the overnight hours. However, the challenge arises when a shift starts on a day and extends to finish on the next day, causing an overlap in workdays for a single shift j, and both days count as workdays for a worker w, as is the case of shifts 4 and 6 of Figure 1. To tackle this issue, we’ve opted for a unified temporal division where each day is divided into 24 units of time (ut), where SS_j and FS_j are respectively the starting and finishing times of shift j. After a certain number of successive days, denoted by SWD, workers must have a day off. A day may consist of one or multiple shifts, and it is crucial for the shipowner to maintain, for each worker, a rest interval Bmin between two successive shifts. In the case of the shipowner, three categories of shift are considered: (1) regular shift, l = 1, refers to standard shift ,(2) reinforcement shift: l = 2, refers to an additional or supplementary shift introduced to bolster the existing workforce for unexpected circumstances or to cover shortages in staffing. The shipowner might assign deck personnel (often sailors) to join the navigating team, (3) premium shift, l = 3, which is designated for transporting hazardous products may come with a risk premium. Therefore, we introduce a binary parameter Bl,j that helps us identify and label which category l that the shift j belongs to. Considering that shifts are classified into different categories with distinct remuneration, achieving fairness in shift assignments is crucial for balanced salaries. Hence, we have introduced an Average Number assignment to category l, ANAl. It designates the average balanced workload to be reached. Each shift is defined by a set number of workers designated as NRP. Given that the shipowner operates various categories of shift moving between categories typically requires an additional qualification obtained either through specific training or after accruing a defined number of hours accompanied by seniors. Therefore, QPw,j defines the qualification of worker w to shift j,QPw,jϵ {0,1}. Given that shifts require different qualifications, this notation indicates whether a worker has the necessary qualifications for a specific shift. We also define a symmetric matrix to illustrate the incompatibility scores Hw,v when worker w works with worker v. Hw,v ranges from 1 to 4, where 1 indicates the lowest level of incompatibility and 4 indicates the highest level of incompatibility. This scale was chosen to simplify the model and maintain a clear distinction between incompatibility levels.

In the upcoming section, we will detail all indexes, decision variables and parameters, along with their application in our model.

4. Problem modeling

The mathematical model consists of four components, which are decision variable, parameters, objective function and constraints.

4.1 Decision variables

Yi,w{=1 if the worker′w′is on duty on day ′i′=0 otherwise

Xj,w{=1 if the the worker ′w′ is assigned to shift ′j′=0 otherwise 

Zw,v,j{=1 if the worker′w′is on duty with the worker ′v′ on shift ′j′=0 otherwise

4.2 Parameters

4.3 Objective function

The overall objective function f aims to minimize two objective functions: f1 and f2.

The first objective function f1 reduces the gap between the number of assignations to category ′l′ and ANAl .The aim is to ensure that all workers have the same number of assignations to category ′l′.

MIN f1=|∑jJ(Xj,w*Bl,j)−ANAl|

We observe that this function introduces non-linearity due to the presence of the absolute value. Therefore, by introducing the auxiliary variable yl,w, we replace the absolute value with two distinct linear inequalities, allowing the problem to be expressed and solved using linear programming techniques. These two inequalities are then transformed into the constraints (10) and (11), as explained in section 3.4. As a result, f1 becomes:

MIN f1=∑w=1W∑l=1Lyl,w

The second objectives f2 is to minimize incompatibility between workers, based on the incompatibility matrix score Hw,v.

MIN=(1w)∑w=1W∑v=1W∑j=1JHw,v*Zw,v,j

It is important to acknowledge that the matrix Hw,v  is symmetric, meaning each interaction between workers w and v is counted twice. Without normalization, this would double the contribution of each interaction. By dividing by the number of workers ( 1w ), we correct for this double counting and ensure each interaction is counted only once, providing an accurate result.

The global objective function f aims to simultaneously ensure workload fairness, represented by f1, and minimize incompatibility, represented by f2. The parameter ∝ represents the weight of f1, while 1- ∝ represents the weight of f2. Therefore, the objective is to minimize f, as shown in the equation:

MIN f=∝f1+(1−∝) f2

MIN f=∝(∑wW∑lLyl,w)+(1−∝)((1w)∑w=1W∑v=1WV∑j=1JHw,v*Zw,v,j)

For the initial solving tests, we assume equal importance with ∝ = 0.5, meaning that both criteria have equal weight in the objective function. In the following sections, we will vary ∝ to understand the relative impact of each criterion on the final solution. By adjusting ∝, we aim to analyze how changes in the weight assigned to each criterion influence the optimization results.

These two objectives depend on several constraints that will be detailed in subsequent sections.

4.4 Constraints

(1) Xj,w≤QPj,w ∀j,∀w

(2)∑j=1J (Xj,w* Ai,j)≤1 ∀i,∀w

(3)∑j=1J(Xj,w*Ai,j)=Yi,w ∀i,∀w

(4)∑w=1W Xj,w=NRP ∀j

(5)Y(i+SWD),w+M*(∑x=ii+(SWD−1)Yx,w−SWD)≤0 ∀i∈{1,..,I−SWD},∀w

(6)Zw,v,j≥1−(M*(2−Xj,w−Xj,v)) ∀w ∀v ∀j

(7)Zw,v,j≤M*Xj,w*Xj,v ∀w ∀v ∀j

Zw,v,j≤Xj,w ∀w ∀v ∀j

(6*)Zw,v,j≤Xj,v ∀w ∀v ∀j

(7*)Zw,v,j≤Xj,v +Xj,w −1 ∀w ∀v ∀j

(8)(Xjb,w*SSjb)−(Xja,w*FSja)−M*((Xjb,w+Xja,w)−2)≥Bmin∀w,∀ ja,∀ jb with ja<jb

(9)Xj,wYi,w Zw,v,j∈{0,1} ∀w ∀v ∀j

(10)Yl,w≥−( ∑j=1J(Xj,w*Bl,j)−ANAl ) ∀w ∀l

(11)Yl,w≥(∑j=1J(Xj,w*Bl,j)−ANAl ) ∀w ∀l

• (1)

  Constraints (1): A worker is scheduled if he is qualified for the shift.

• (2)

  Constraints (2): Each worker is either assigned to one shift per day or not assigned to any shift.

• (3)

  Constraints (3): A worker is on duty for a shift if he is not on rest day.

• (4)

  Constraints (4): A shift must have a required number of workers.

• (5)

  Constraints (5): Every worker should have a day off after a set of consecutive workdays.

• (6)

  Constraints (6) and (7): A worker w is either assigned on duty with worker v in shift j or not assigned together.

• (7)

  Constraints (6*) and (7*): Constraints 6 and 7 are initially in nonlinear form, and we have applied standard techniques to linearize them.

• (8)

  Constraints (8): Between two shifts, a worker should have minimum rest hours.

• (9)

  Constraints (9): The decision variable is made binary

• (10)

  Constraints (10) and (11): linear constraints that ensure that all workers work the same number of shifts of the category l.

5. Experimental results

Once the mathematical model is established, it must be executed to validate its effectiveness and ensure that objectives are met and constraints are respected. This involves implementing the model into a computational algorithm using the FICO Xpress optimizer. The model is executed on a laptop equipped with an Intel Core i7-10700K processor, boasting a clock speed of 3.80 GHz (3,792 MHz), 8 physical cores and 16 logical processors, supported by 32GB of RAM, and running on the Windows 10 operating system. The results are then analyzed in two sections: first, we focus on testing the model to ensure its effectiveness and if the model does not meet the objectives or violates constraints. The second section conducts a sensitivity analysis that involves understanding how changes in input parameters affect the model’s outputs.

5.1 Model validation

To test and validate the model, we present examples tested on the instance showed in Table 1, with QPj,w and H_w,v hereafter presented. We chose to use small instances to simplify and better understand the problem. The aim is to check if the model appropriately assigns the workers while fulfilling the objectives and adhering to the previously mentioned constraints.

QPj,w (0w1w2w3w4j11111j21111j31111j41111j51111)

Hw,v(0w1w2w3w4w10111w21011w31101w41110)

5.1.1 Ensuring fair assignment of shifts

Since one of our primary objectives is to ensure fairness, we will evaluate whether the program maintains equitable assignment among workers. To do that, we assume that all workers are qualified and compatibles, see the matrix  Hw,v and QPj,w. The result is presented in Figure 2.

According to Figure 2, the program assigns workers to shifts in a fair and equitable way, with two individuals per shift NRP = 2, ensuring that each employee w is assigned to different shift categories, 2 categories of shift per person in this example. In the tested instances, w4 is assigned to two shifts: j2 and j3. However, it’s important to note that shift j3 is considered to belong to the day i₃, and not to i₂, due to the model’s assumption that shifts starting on day i and ending on day i+1 are considered to belong to day i+1. Given that we are testing the program on small instance with 4 shifts/workers, we pre-defined shifts in a way that shifts are spaced through the time horizon and Bmin is systematically respected. Therefore, in section 5.1.2, we will focus on reducing the time interval between two consecutive shifts, in order to not exceed Bmin. This will allow us to verify both the adherence to Bmin and that a worker cannot perform two shifts on the same day.

5.1.2 Validation of the minimum break duration and single shift per day constraint

In this section, we verify whether the program adheres to the minimum break duration Bmin requirement. On the day i₄, two shifts j₄ and j₅ are planned for testing the constraint 8.

According to Figure 3, the program successfully identified that workers w₁ and w₃ were not eligible for assignment to j₅; they were already scheduled to work on the same day in the shift j₄. The program recognized that the minimum break duration Bmin was not respected between the two shifts, leading to the assignment of workers w₂ and w₄ instead, which confirms our initial hypothesis.

5.1.3 Assessing the program’s ability to handle QPj,w and Hw,v

In this scenario, we will assess the program’s ability to manage incompatibility. Specifically, we have chosen two individuals, w₁ and w₂, who typically work together and were initially assigned to the same shift j₁.

As shown, H12 and H21 was set to 1 at first, indicating a good working relationship. However, we later adjusted their compatibility level to 4, indicating that they were no longer compatible. Additionally, we assume that w₁ is not qualified to perform j_1.

In Figure 4, we show that w₁ not assigned to j₁, and notably, w₁ and w₂ did not work together in any shift. This outcome highlights the program’s ability to provide a fair schedule that minimizes workers incompatibility while adhering to qualification constraints and the breaks’ respect.

5.2 Sensitivity analysis

After testing our model, evaluating its performance is crucial. This involves studying how changes in input parameters affect the model’s outputs, providing insights into the model’s behavior and effectiveness. In this study, we firstly varied QPj,w to evaluate its impacts on the objectives. Then, we explored the model’s execution time limits by varying w. However, it is essential to note that these experiments rely on the generation of specific instances to create relevant scenarios.

5.2.1 Instance generation

The aforementioned two studies are based on the data presented in Table 2. The only difference is that in the second study, the parameter w will be varied.

The minimization of incompatibility highly depends on H_w,v this means that even a minor change in that a simple change on Hw,v could significantly impact the results. Relying on a random matrix may not reflect significant results due to the large number of configurations that could exist. Therefore, we need further robustness exploration to confirm if our results remain reliable when the H_wv is modified.

Consequently, we create the values of H_wv for different scenarios. Thus, we created a compatibility scale that categorizes the level of incompatibility between two workers into four distinct levels: highly compatible, compatible, moderately compatible and incompatible; each level is represented by a number ranging from 1 to 4, respectively (see Table 3).

In the following, we categorize levels 1 and 2 as the compatibility class, and levels 3 and 4 as the incompatibility class. While we do not consider the specific distribution of percentages between the sub-classes (levels) within each class, it is important that the total percentage of levels within a class meets the required percentage. For instance, a matrix may consist of 70% compatibility, meaning that level 1 and 2 together make up 70% of the entries in the matrix.

Using the aforementioned compatibility scale, we concentrated our analysis on specific compatibility scenarios that explore various distributions within a single matrix, such as:

• (1)

  Scenario 1: 70% of compatibility class and 30% of incompatibility class (meaning 70% of the matrix values are either 1 or 2 and 30% of are either 3 or 4).

• (2)

  Scenario 2: 50% of compatibility class and 50% of incompatibility class.

• (3)

  Scenario 3:30% of compatibility class and 70% of incompatibility class.

We’ve provided an example of a matrix sized 10x10. This matrix illustrates the compatibility level among a group of 10 workers. Each worker is represented both in the rows and columns, emphasizing the symmetry of the matrix. This symmetry has two important implications: firstly, Hw,v is identical to Hv,w. Secondly, the matrix has zero values on the diagonal, indicating that a worker’s compatibility with themselves is not applicable.

Hw,v=(0w1w2w3w4w5w6w7w8w9w10w10111113213w21012141424w31104221311w41240223224w51122032133w61422302211w73113220212w82432122042w91212311401w103414312210)

In the provided matrix, we applied the first scenario and assumed a distribution of 70% compatibility, where 35% of the cells contain the value 1 and another 35% contain the value 2. For the incompatibility class, which makes up 30% of the entries, 15% of the cases contain the value 3 and the remaining 15% contain the value 4. For each scenario, we generate 10 different matrices, not directly adhering to the subclasses (levels) distribution but rather to the distribution of incompatibility/compatibility classes.

In the next sections, we randomly generate different matrix of Hw,v using the explained three scenarios.

5.2.2 Impact of the workers qualification on the objectives

In this section, we choose to vary QPj,w due to its significant impact on SS. It is important to highlight that worker qualification generates a costs. This is due to the training that workers must undergo for a certain number of hours to achieve a particular skill level.

This study consists to vary, at each step, QPj,w from 50% to 100%, with a step of 10% to evaluate its impact on the objectives for 10 different H_w,v. 50% means that half of the workers are qualified, while 100% means that all workers are qualified. However, when generating QPj,w we do not select the shifts for which the workers will be qualified. These steps are identically applied to all three different scenarios resulting in a total of 180 = 6*10*3 different instances, 6 matrices of QPj,w and 3 scenarios of compatibility tested on 10 instances. Throughout this process, we evaluated the effects of these changes on f, f₁ and f₂. This approach involves conducting the analysis by comparing results when transitioning from one percentage to another one progressively; starting from 50% means that no comparisons are made with previous levels, resulting in zero gain percentages for the objective functions generated in this case. However, in the subsequent cases, from 60% to 100%, the gain is calculated in a comparison with 50% to highlight the progression.

The results are presented in Table 4.

In Table 4, we observe that the gains of f, f₁ and f₂ increase proportionally with the percentage of qualified workers. This trend highlights the positive influence of qualification on the overall objective functions. Since there are several qualified workers, it is easier to find a fair scheduling with fewer incompatibilities. Notably, the increase in gain of f is more significant in the first scenario compared to the other scenarios, indicating that the program has a greater ability to assign workers when they are more compatible, leading to higher profit gains. However, to obtain a comprehensive understanding of the impact of QPj,w, we have calculated the average profit gains of f, f₁ and f₂, for each qualification level over three scenarios. Results are shown in Figure 5, which illustrates that increasing qualification, from 50% to 80%, leads to a significant improvement. This can be attributed to the program’s access to a larger pool of qualified workers, making it easier to find combinations of workers that can work effectively together, thus reducing compatibility issues while maximizing equity profit.

Beyond 80%, gains start to increase only marginally or may even stagnate for certain objective functions such as fairness.

This behavior could indicate either a threshold in the model’s optimization is reached or meeting the boundaries of optimality, where future improvements might be marginal. In such cases, future improvements might be marginal, such as fairness, where the model has reached its limits at 70% of the qualification level, signifying its capacity to maintain an optimal workload balance and any further increase in qualifications beyond this threshold may potentially incur additional costs without significant added value in the objectives’ gains.

The results show that an increase in the percentage of qualified workers generally leads to significant improvements in the objective functions. They also reveal the positive impact of the compatibility increasing on the profit’s gains. However, in the real world, the distribution of Hw,v may not always follow a predictable pattern. Factors such as personality differences, varying levels of experience and differing skill sets can influence workers’ collaboration. Therefore, testing with a random matrix provides decision-makers with a more comprehensive understanding of potential outcomes across diverse and unpredictable conditions they might face. To do so, we will test our model using randomly generated Hw,v and observe if we can confirm the previous curve. The outcomes of these tests are presented in Table 5.

According to Table 5, we observe similar behavior when Hw,v is predefined, with the gain increasing proportionally to the number of qualified workers. This trend is further supported by Figure 6, which shows curves remarkably similar to those in Figure 5. However, fairness reaches its threshold at 60% of qualified workers in this case, compared to 70% in the previous analysis. Therefore, the random nature of Hw,v introduces greater uncertainty in predicting specific levels of gains, making it challenging for decision-makers to pinpoint exact outcomes.

The comparison highlights that predefined scenarios provide clear trends but may not capture real-world complexity, while random matrix provides a more realistic but introduces uncertainty in predicting specific outcomes.

Although our previous study reflects general trends and directions, it does not fully explore the limits of the model and the factors that could increase its complexity. This will be elaborated in Section 5.2.3.

5.2.3 Exploring the impact of the number of workers and incompatibility levels on the execution time

As a fundamental parameter in SS, the number of workers is a key factor whose importance extends far beyond the composition of work teams. In this study, we analyze how the worker size impacts the execution time. Thus, Table 6 presents the execution time in second for different W in the 3 scenarios.

In this study, we assumed that all workers were fully qualified and investigated how varying the number of workers, under the three different compatibility scenarios, impacted the execution time of the program.

We established a baseline of 9 workers, determined by input data constraints, and then iteratively increased this number to 14. For each problem size, we consistently applied the same parameters that were already used in the previous section.

Table 6 shows that execution time increases proportionally with the number of workers. The execution time is also influenced by the level of incompatibility; it is noticeable that as the number of incompatible workers increases, the execution time extends eventually reaching a stopping point when W = 14. For the first scenario, an execution time of 79,085 s was recorded. However, for the subsequent scenarios, the running time surpassed 24 h without producing any results, making further continuation of the process impractical.

To confirm the trend observed in Table 6, we can refer to Figure 7, which shows the curve of execution time in function of W and incompatibility levels.

Figure 7 reveals that higher incompatibility results in longer execution times. For example, when W = 12, an execution time of 86.846 s is recorded when 70% of workers are compatible. However, when only 30% of workers are compatible, the execution time increases significantly to 165.250 s. This trend is observed across all problem sizes, suggesting that the optimization process becomes increasingly complex as worker incompatibility increases, leading to longer execution times.

Figure 7 not only illustrates the impact of incompatibility on the execution time but also demonstrates the effects of increasing the workforce size since the time scale increases in each case of W. To further clarify this relation, Figure 8 presents the average execution times of the three different scenarios, for each case of W, from 9 to 13 workers.

The idea behind averaging the execution time is to mitigate the potential ambiguity caused by the significant deviation of execution time values across different scenarios for each workforce size. This deviation makes it difficult to align these values on the same scale, leading to potential ambiguity in interpreting the curve.

As illustrated in Figure 8, the execution time tends to increase as the number of workers grows, particularly when W = 13, resulting in an execution time of 1335.20 s. This phenomenon can be attributed to two factors. Firstly, a larger workforce leads to an exponential increase in possible combinations to evaluate, necessitating more computational time or demanding greater computational resources. Secondly, the input data also has an impact on the solution, as working with fewer instances makes it increasingly complex to distribute workers throughout the horizon and shifts while respecting constraints and meeting the objectives.

6. Conclusion

This paper presents a novel model for staff scheduling problems in the maritime transportation sector, which is based on a real-world case study and can be adapted to other domains due to its generic nature. The novelty of this work lies in the incorporation of worker incompatibilities as an objective, while also prioritizing workload fairness and adhering to various constraints, such as qualifications, rest hours, the number of workers per shift and days off. This problem is mathematically formulated as an MILP model, implemented using XPRESS solver and complemented by experimental results that evaluate the model’s performance under varying parameter adjustments. This study has enabled us to draw significant conclusions regarding the behavior of the proposed model, offer valuable managerial insights and outline promising future perspectives.

6.1 The behavior of the proposed model

• (1)

  Increasing the number of qualified workers typically results in significant improvements in gains, but these gains can reach a limit at a certain worker qualification level. Further increases in qualification beyond this threshold may incur costs without adding value to the gain profit.

• (2)

  Ensuring compatibility between workers has a positive impact on profits. This influence was observed in two studied cases: randomly generated compatibility matrices and predefined compatibility scenarios. Thus, the predefined scenarios offer clear interpretations but may not reflect real-world complexity, while the random matrices case provides a more realistic assessment, it introduces uncertainty in predicting the level of gain profit that a decision-maker could.

• (3)

  Execution time can increase not only with the growing number of workers but also with incompatibility between them, leading to excessive execution times or even the inability to find a solution for certain group sizes of workers.

6.2 Managerial insights

Our model highlights the importance of considering worker compatibility and qualifications in scheduling decisions. Addressing these factors can lead to more balanced and efficient schedules. Hiring motivated, team-oriented individuals fosters better compatibility within teams, reduces conflicts and improves overall productivity. While investing in training may require significant upfront costs, it enhances workers' adaptability to different shifts and roles, ultimately increasing operational efficiency. Prioritizing both the right talent and continuous development creates a workforce that is better equipped to handle the demands of a dynamic work environment.

6.3 Perspectives

The development of a mathematical model is essential to gain a deep and precise understanding of the problem at hand. Demonstrating that the problem is NP-hard provided a theoretical foundation justifying the subsequent use of approximative methods. This foundation not only strengthens the credibility of our solutions but also facilitates effective validation and benchmarking. However, our study shows that for larger instance sizes, the computation time becomes significant, revealing challenges for practical real-life applications where quick decision-making is crucial. Future work will explore advanced heuristic techniques, informed by the insights gained from our mathematical formulation. These methods also allow us to expand our problem scope by considering additional constraints such as workers’ seniority, individual worker preferences and other relevant factors which are not addressed in this model.

Figures

Figure 1

Model structure

Figure 2

Fair scheduling with predefined shifts and overlap days

Figure 3

Adherence to the minimum break duration and single shift per day

Figure 4

The impact of adjusting QPj,w and Hw,v

Figure 5

Average gains of objective functions in function of qualified workers percentage

Figure 6

Average gains of objective functions using random instances of Hw,v

Figure 7

Illustration of execution time variations based on the number of workers and their compatibility

Figure 8

Effect of increasing worker count on execution time: (average across three scenarios)

Table 1

Example instance for testing and validating the model

I	4
J	5
W	4
NRP	2
Bmin	8
alpha	0.5

Source(s): Authors’ own work

Table 2

Initial parameters used in sensitivity analysis

Parameters	Value
α	0.5
NRP	2
W	10
I	6
J	9
L	3
SWD	5
Bmin	8
w	{9,..,14}
QPj,w	From 50% of qualified workers to 100% of qualified workers

Source(s): Authors’ own work

Table 3

Scale for categorizing incompatibility levels

	Levels		Significance
Compatibility class	Highly compatible	1	Workers have strong preferences to work together and collaborate effectively
	Compatible	2	Workers generally prefer to work together, although there may be some minor differences in their preferences or work styles
Incompatibility class	Moderately incompatible	3	Workers have significant differences in their preferences or work styles, which can sometimes lead to friction or inefficiencies
	Incompatible	4	Workers have very different preferences or work styles, often resulting in conflicts or difficulties in working together

Source(s): Authors’ own work

Table 4

Impact of qualified workers’ percentage on the objective functions for different incompatibility levels

%Qualified workers	Average f2	Average f1	Average f	% of compatibility profit	% of fairness profit	% of objective function profit
70% compatible and 30% incompatible
50%	11.76	13.3	12.53	0%	0%	0%
60%	10.74	11.44	11.1	9%	14%	11%
70%	8.76	9.8	9.28	26%	26%	26%
80%	7.98	9.8	8.89	32%	26%	29%
90%	7.63	9.80	8.74	35%	26%	30%
100%	7.30	9.8	8.39	38%	26%	33%
50% compatible and 50% incompatible
50%	10.08	13.42	11.75	0%	0%	0%
60%	9.22	11.58	10.4	9%	14%	11%
70%	7.56	9.8	8.68	25%	27%	26%
80%	7.08	9.8	8.44	30%	27%	28%
90%	6.58	9.8	8.19	35%	27%	30%
100%	6.52	9.8	8.16	35%	27%	31%
30% compatible and 70% incompatible
50%	14.96	13.12	14.04	0%	0%	0%
60%	13.94	11.4	12.67	7%	13%	10%
70%	11.52	9.8	10.66	23%	25%	19%
80%	10.6	9.8	10.2	29%	25%	27%
90%	9.82	9.8	9.81	34%	25%	30%
100%	9.72	9.8	9.78	35%	25%	30%

Source(s): Authors’ own work

Table 5

Impact of percentage of qualified workers on the objective functions

% of qualified workers	Average f2	Average f1	Average f	% of compatibility profit (f2)	% of fairness profit (f1)	% of objective function profit (f)
50%	11.45	10.8	11.05	0%	0%	0%
60%	10.08	5.38	7,855	12%	50%	29%
70%	8.65	5.4	7.02	24%	50%	36%
80%	8.14	5.4	6.77	29%	50%	39%
90%	7.66	5.4	6.53	33%	50%	41%
100%	7.56	5.4	6.48	34%	50%	41%

Source(s): Authors’ own work

Table 6

Impact of the number of workers and incompatibility levels on execution time

	W = 9	W = 10	W = 11	W = 12	W = 13	W = 14
	Execution time (second)
70% compatibility, 30% incompatibility	2.19	3.36	9.09	86.84	694.25	79,085
50% compatibility, 50% incompatibility	2.21	4.37	31.12	100.56	870.23	> 24h
30% compatibility, 70% incompatibility	2.30	7.28	43.370	165.25	2431.12	> 24h

Source(s): Authors’ own work