Ant colony algorithms for minimizing costs in multi-mode resource constrained project scheduling problems with spatial constraints

* Corresponding author E-mail [email protected] (M. P. de la Pisa) ISSN 1923-2934 (Online) - ISSN 1923-2926 (Print) 2024 Growing Science Ltd. doi: 10.5267/j.ijiec.2024.5.002 International Journal of Industrial Engineering Computations 15 (2024) 667–684 Contents lists available at GrowingScience International Journal of Industrial Engineering Computations home p a g e: www.Growin g Science.co m /i j iec Ant colony algorithms for minimizing costs in multi-mode resource constrained project scheduling problems with spatial constraints Miguel P. de la Pisaa*, Jose C. Molinaa and Ignacio Eguíaa aDepartment of Industrial Management, University of Seville, Camino de los Descubrimientos, 41092, Sevilla, Spain C H R O N I C L E A B S T R A C T Article history: Received March 26 2023 Received in Revised Format April 28 2024 Accepted May 5 2024 Available online Ma y 5 2024 This paper addresses the problem of activity scheduling and operator assignment in workstations of aerospace assembly lines. The problem is modelled as a new variant of the Multi-Mode Resource Constrained Project Scheduling Problem (MRCPSP), which incorporates practical features from aerospace workstations in assembly lines. These workstations have a substantial number of activities to be scheduled within a given assembly cycle time. It introduces particularities which are not usually addressed such as considering additional workers for performing activities, different workers’ proficiency, and spatial limitations in work zones. The objective is to schedule the activities of an aerospace workstation, minimising the total labour cost, while satisfying the cycle time and the zone’s limitations. The problem is initially formulated by employing mixed-integer linear programming methods with mathematical modelling and solved using two different algorithms: an Ant Colony System (ACS) and a memetic ACS. Given the novelty of the problem presented, new sets of benchmark cases of different sizes for this problem are also proposed and solved. To assess the performance of the algorithms, the solutions for the small-sized instances are compared in terms of deviation with the results obtained by an optimisation modelling software. Further experimentation with the algorithms is carried out with medium and large instances, showing good performance and providing reasonably good results in realistic problems. © 2024 by the authors; licensee Growing Science, Canada Keywords: Multi-mode resource constrained project scheduling Ant colony system Memetic algorithm Spatial constraints Aerospace 1. Introduction The aerospace industry has been at the vanguard of production methods for decades. Nevertheless, the need to remain competitive in terms of resource reduction, adapting to customers' requirements, and embracing the new digital paradigm of Industry 4.0 calls for further action to achieve even more efficient and flexible production systems. Scheduling plays a crucial role in optimising operations, but despite the high level of digitisation in the aerospace industry, scheduling processes have remained largely unaffected, with most activities being planned manually based on expert knowledge (Borreguero 2019). Aerospace Assembly Lines (AAL) scheduling problems are a variation of the well-known assembly line scheduling problem that considers the characteristics of the aerospace sector, such as low production rates, labour-intensive operations, and many tasks per product (Heike et al. 2001). These lines are mainly manual and paced. Since the failure to deliver on time may result in significant penalties for the manufacturer, it is crucial to meet schedules at each workstation of the AAL (Arkhipov et al., 2018). For the purposes of optimising the overall operations of an AAL, the first phase is to equitably distribute the tasks amongst the set of defined workstations, whilst also assigning the available workforce to each workstation. This problem is recognised as the assembly line worker assignment and balancing problem (ALWABP) originally defined by Miralles et al. (2007). The main objective of the ALWABP is the assignment of tasks to workstations such that the expected cycle time is minimised for the available workers (Ritt et al. 2016). This paper is focused on the following phase where tasks are assigned to workers at each workstation to find an optimal schedule of task processing that satisfies aerospace workstations constraints. The aerospace workstation scheduling problem contains features that are inherent to this particular manufacturing environment. First, workers may have different skills and proficiency levels which may result in different labour costs and execution times. Second, activities can be processed in several alternative modes, depending on the number of workers 668 assigned for the execution. As well as this, each mode for an activity is defined by a combination of operator skills and proficiency levels, number of operators and durations (Borreguero 2015). Finally, workstations are divided into smaller areas where a limited number of workers can operate simultaneously. There has been little research on aerospace workstation scheduling, taking into consideration its distinctive characteristics. Borreguero et al. (2015) presented a mixed-integer linear programming (MILP) model to reduce labour costs. This model includes various execution modes for tasks, as well as constraints on zones and cycle time. Russell and Taghipour (2019) formulated a set of discrete-time multi-objective MILPs whose objectives include minimising makespan, incomplete activities, resource requirements, and deviations from cycle time and budget. The framework also considers activities with multiple resources and modes, with a maximum allowable capacity for work zones. Based on the motivation behind this study, there are two main scientific contributions presented. The first is the formal definition of the aerospace workstation scheduling problem as a variant of the Multi-Mode Resource-Constrained Project Scheduling Problem (MRCPSP) which considers zone restrictions. The problem is referenced as MRCPSP-Z and is modelled using mixed-integer linear programming techniques. Realistic factors of AAL workstations, such as maximum cycle time, work zone limitations, and the number of available workers with varying proficiency levels are considered with the objective of minimizing the Total Labour Costs (TLC). The second contribution is the development of two different optimization approaches for addressing the MRCPSP-Z: (i) an Ant Colony System (ACS) algorithm, and (ii) a novel Memetic ACS (MACS) algorithm that combines ACS with a Variable Neighbourhood Descent (VND) algorithm. Both approaches incorporate a cost-peak-reduction mechanism aimed at enhancing the efficiency of generating improved solutions. To demonstrate the efficiency of ACS and M-ACS, tests are carried out on a newly created set of MRCPSP-Z instances. This paper is organised as follows: Section 2 presents a summary of related research, including variants of the problem and corresponding methodologies. Section 3 describes the problem's characteristics, including a mathematical model formulation for the MRCPSP-Z. A description of the main components of the approaches is provided in Section 4. The parameter settings and experimental results obtained from problem instances are presented in Section 5. Finally, conclusions are provided in the final section. 2. Literature review The scheduling of operations in an aerospace workstation can be viewed as a specific application of the Resource-Constrained Project Scheduling Problem (RCPSP), which aims to determine the start/finish time of a set of activities subject to some precedence relations and a certain number of available resources. In AALs, the main resources are workers, as workstations are characterised by labour-intensive operations. However, the RCPSP may not account for all situations occurring in practice. Three extensions are considered to adapt the RCPSP for the scheduling of activities in a workstation of AAL: (i) setting minimum and maximum number of workers to perform each activity, (ii) a set of workers with different skills and proficiency levels, and (iii) a maximum allowable number of workers in each workstation area. Moreover, minimizing overall labour costs constitutes a crucial factor in achieving efficient task scheduling within an AAL. The standard RCPSP has only one way of performing each activity, whereas in the aerospace environment some operations could be performed in different ways depending on the number of assigned workers. This feature is contemplated in the MRCPSP, which arises when each activity can be processed in several alternative modes. As a result, the duration of each activity mode relies on the number of workers assigned to it. Dolgui et al. (2018) presented a MILP model with the objective of minimising the cycle time for scheduling on a paced assembly line, where the operation time varies depending on the number of workers assigned to the activity. Baradaran et al. (2012) investigated the MRCPSP within a Programme Evaluation and Review Technique (PERT) network. Their work introduced a list of execution modes outlining the various resource combinations required to complete an activity. The multi-skill RCPSP can be considered as a particularisation of the MRCPSP. In their respective studies, Povéda et al. (2023) and Li et al. (2024) approached this extension by defining the activity modes as all the possible combinations of resources possessing the required skills. Expertise level has a direct impact on performance, as there is a progression from a newcomer to an expert worker. The second extension of the standard RCPSP accounts for the varying expertise of operators, which affects the model in diverse ways. The most prevalent application of this extension involves considering that worker level affects task duration and labour cost. Therefore, this second extension can also be modelled as multiple modes of executing operations in an MRCPSP. Cheng and Chu (2012) examined the processing duration in relation to workers' proficiency levels, defined in the range of [0-1], and the increase in the unitary labour cost based on the worker's experience. It is also possible to incorporate the proficiency level into the goal. Shahnazari et al. (2017) aimed to minimise the utilisation of less skilled workers as part of the objective function. Finally, Ahmadpour and Ghezavati (2019) have argued that the critical activities can only be assigned to workers with a certain expertise level. The use of platforms and gigs is prevalent in aerospace workstations to enable easier access to large components. This consequently restricts the working area to a maximum number of personnel, which is considered a third extension of the standard model. The restriction of the maximum number of workers in a specific area is a frequent application in research (see e.g. Kadrou & Najid 2006), so this third extension is modelled as a new constraint. M. P. de la Pisa et al. / International Journal of Industrial Engineering Computations 15 (2024) 669 The RCPSP and its variants are widely recognised as strongly NP-hard (Blazewicz et al., 1993). Consequently, numerous authors have developed heuristics and metaheuristics to achieve good solutions within reasonable running times. In their review, Van Peteghem and Vanhoucke (2014) provided an overview of existing metaheuristic solution procedures for MRCPSP, including Simulated Annealing, Genetic Algorithms (GA), Particle Swarm Optimisation (PSO) and other approaches. Pellerin et al. (2020) conducted a survey on hybrid approaches for RCPSP, which explored the combination of local search strategies with population-based metaheuristics and the sequential or parallel execution of potentially different pure metaheuristics that exchange information about the search process. The most similar research to the proposed MRCPSP-Z is introduced in Kadrou and Najid (2006). They developed a new version of the parallel schedule generation scheme (PSGS) heuristic through the inclusion of priority rules used in a multiskill MRCPSP with limited zones for minimizing the makespan. The technique is applied to a set of generated instances and the results are compared to other heuristics. In previous studies, Ant Colony algorithms have effectively been used to solve MRCPSP. Shan et al. (2007) introduced a single pheromone approach for selecting activity-modes, alongside a global and local pheromone update strategy. Chiang and Huang (2012) investigated PSGS as a solution presentation method, and a dynamic tournament strategy was designed to find a balance between local optima and infeasible solutions during the exploration phase. Li and Zhang (2013) examined the serial schedule generation scheme (SSGS) to construct the scheduling using two independent pheromones for activity sequence and mode selection. Wuliang et al. (2014) proposed the use of a pool of priority rules as heuristic information and a branch and bound mechanism to discard infeasible paths before selecting the next activity during solution construction. Ant Colony algorithms often use the optional local search phase extensively. The aim is to increase efficiency by improving the solutions constructed by ants using a local search algorithm. However, producing appropriate initial solutions for local search algorithms is a difficult task. Empirical evidence suggests that the probabilistic and adaptive solution generation process of ant colony algorithms is well-suited for this purpose (Dorigo et al., 2006). When a population-based global search approach is intensified with a local search procedure, the resultant method may be identified as a memetic algorithm (Moscato, 1989). Different approaches of memetic algorithms have been proposed to solve the MRCPSP in scientific research. Shen and Li (2013) suggested employing a PSO algorithm with a two-stage local search. The first step increases the level of resources to an activity to reduce the processing time. The second step is a swap strategy of adjacent activities. Khalilzadeh (2015) proposed a Honey Bee Swarm Optimization approach that incorporates a delay local search. This technique is performed by a mutation operator that delays scheduling each activity, regardless of its priority, to enable other activities to be scheduled earlier while preserving resources for other activities. Afshar et al. (2022) presented a GA with a local search component that applies mode permutation to activities on the critical path. This paper presents the MRCPSP-Z. To the authors' best knowledge, no approach has been developed that specifically utilises ACS algorithms to address the MRCPSP, while considering zone limitations, minimum and maximum worker requirements for specific tasks, and variations in workers' skill levels that impact activity duration and costs. 3. Problem description and mathematical model The Multi-Mode Resource Constrained Project Scheduling Problem with zone restrictions (MRCPSP-Z) is defined by a tuple (V; M; p; E; R; B; b; Z; Wz, wz) where: - V = {A0, A1,…, An, An+1} is a set of activities. Activities A0 and An+1 are dummy activities, representing, by convention, the start and the end of the schedule. The set of non-dummy activities is defined by A = {A1,…, An}. - M ∈ℕ is a vector of naturals, being Mj the number of modes that activity j can execute, with M0 = Mn+1 =1, and 𝑀≥1 ∀𝐴∈𝐴. - p is a vector of vectors of naturals, being Pjm the duration of activity j using mode m, with 1 ≤𝑚≤𝑀. For the dummy activities P0,1 = Pn+1,1 =0, and 𝑃>0 ∀𝐴∈𝐴,1≤𝑚≤𝑀. - E is a set of pairs of activities representing precedence relations. Concretely, (Ai, Aj) ∈ E iff the execution of activity Ai must precede that of activity Aj, i.e., activity Aj must start after activity Ai has finished. Thus, all precedence relations between activities are considered finish-to-start with zero lag, A0 is a predecessor of all other activities and An+1 is a successor of all other activities. - R = {R1,… ,Rv-1, Rv, Rv+1,… ,Rq} is a set of resources. The first v resources are renewable, and the last q-v resources are non-renewable. - B ∈ℕ is a vector of naturals, being Bk the available amount of each resource Rk. - b is a matrix of naturals corresponding to the resource demands of activities per mode. The value bjkm represents the amount of resource Rk used during the execution of activity Aj in mode m. For the dummy activities b0,k,1 = bn+1,k,1 =0 ∀𝑘∈{1, … , 𝑞}. - Z = {Z1,… ,Zm} is a set of work zones. - WZ ∈ℕ is a vector of naturals, being WZz the capacity of each zone Zz, i.e, maximum amount of renewable resources allowable at any time in zone Zz. 670 - wz is a vector of vectors of binaries, being wzjz equal to 1 if activity j is processed in zone z. Only one zone per activity. A schedule is a vector of naturals S = (S0, S1,…, Sn, Sn+1) where Sj denotes the start time of activity Aj, and considering that S0 = 0. A schedule of modes is a vector of naturals SM = (SM0, SM1,…, SMn, SMn+1) where SMj, satisfying 1≤𝑆𝑀≤𝑀, denotes the mode of each activity Aj. A solution to an MRCPSP instance is a schedule of modes SM and a schedule S, subject to the precedence relations, the resource constraints, and the zone limitations, and considering an objective function such as minimal makespan (Sn+1) or minimal number of resources used. As mentioned before, the aerospace workstation scheduling problem is a particular case of the Multi-Mode Resource Constrained Project Scheduling Problem with zone restrictions (MRCPSP-Z). The following assumptions are considered in this problem that differs from the standard MRCPSP-Z: - All resources are renewable from period to period and are associated with a set K = {1,…, k,…, K} of individual workers. - A set of worker profiles F = {1,…, f,…, F} are defined. A worker profile is associated to one worker skill and one proficiency level in that skill. - D is a vector of vectors of binaries, being Dkf equal to 1 if profile f is mastered by worker k, so that, each individual worker k∈K corresponds to only one profile f∈F. - Each activity requires a variable number of workers of certain profiles. The variable number of workers required for each activity Aj∈A and the different profiles that could perform the activity Aj, generate several execution modes Mj for each activity Aj. Then, wb is a matrix of naturals corresponding to the resource demands of activities per mode. The value wbjmf represents the number of workers with profile f used during the execution of activity Aj in mode m. For the dummy activities wb0,1,f = wbn+1,1,f =0 ∀ f∈F. - The cycle time (C) of the aerospace assembly line is a parameter of the aerospace workstation scheduling problem and is considered as a limitation in which the ending activity assigned to the workstation must be completed: 𝑆≤𝐶. - The objective of the proposed problem is to determine the best assignment of the available workers to the activities in order to minimise the total labour costs per unit of time (TLC) in the workstation. Then, WC ∈ℝ is a vector of reals, being WCk the unitary cost of the individual worker k∈K. While the main objective of RCPSP is to reduce the total project duration or makespan, AAL stations follow a fixed cycle time for completing all tasks assigned to each workstation in a synchronous line. It is worth noting that finishing a task in a single workstation prior to the stipulated cycle time is unproductive since the assigned workers will remain idle until the next cycle, despite still counting for costing calculations. A new mixed-integer linear programming formulation is proposed for the MRCPSP-Z applied to the aerospace workstation based on the continuous-time formulation proposed by Correia et al. (2012) for the resource-constrained project scheduling problem with multi-skill resources (MSRCPSP). This model is extended to include the cycle completion time and the spatial limitations of the workstation in AALs. The spatial constraints make it necessary to include variables with a discrete-time formulation. The new proposed model makes use of the following notation: Sets: V = {A0, A1,…, An, An+1} Set of activities. Activities A0 and An+1 are the dummy activities E ⊆ V × V Pairs of activities (i, j) such that Ai directly precedes Aj N ⊆ V × V Pairs of activities which have no precedence relations K = {1,…, k,…, K} Set of individual workers F = {1,…, f,…, F} Set of worker profiles Z = {1,…, z,…, Z} Set of work zones T = {1,…, h,…, t,…, C} Set of time periods during the cycle time Parameters: Mj amount of execution modes of activity Aj (Aj ∈ V; 𝑀≥1); M0=Mn+1=1 pjm processing time of activity Aj using mode m wbjmf number of workers of profile f required by the mode m of activity Aj. The dummy activities have no profile requirements: wb0,1,f = wbn+1,1,f =0 ∀ f∈F C cycle time of the assembly line M. P. de la Pisa et al. / International Journal of Industrial Engineering Computations 15 (2024) 671 WZz capacity of zone z, i.e., maximum number of workers allowable at any time in zone z Dkf=1 if profile f is mastered by worker k. Only one profile per worker wzjz=1 if activity Aj is processed in zone z. Only one zone per activity WCk unitary cost of worker k UBS upper bound of the start time of any activity UBW upper bound of the number of activities a worker can contribute Variables: Sj start time of activity Aj (Aj ∈ V), that is, the schedule (S) SMjm=1 if activity Aj is executed in mode m (Aj ∈ V, 1≤𝑚≤𝑀), that is, the schedule of modes (SM) Uij=1 if activity Ai is completed before activity Aj starts (Ai, Aj ∈ V ∧ (i, j) ∈ N) Wjk=1 if worker k contributes to activity Aj (Aj ∈ V, k ∈ K) Xjmt=1 if activity Aj using mode m is completed exactly at time t (Aj ∈ V, 1≤𝑚≤𝑀, t ∈ T) Ok=1 if worker k contributes at least to one activity (k ∈ K) TLC total labour cost of workers used in the AAL station per unit of time. Model: 𝑚𝑖𝑛 𝑇𝐿𝐶 (1) 𝑠.𝑡., 𝑆≥𝑆+𝑝·𝑆𝑀 ⬚ 1≤m≤Mi ∀(𝑖, 𝑗 󰇜∈E (2) 𝑆≥𝑆+𝑝·𝑆𝑀−𝑈𝐵𝑆·1−𝑈 ⬚ 1≤m≤Mi ∀(𝑖, 𝑗 󰇜∈N (3) 𝑈+𝑈≤1 ∀(𝑖, 𝑗 󰇜∈ N (4) 𝑊·𝐷 ⬚ ∈K =𝑤𝑏·𝑆𝑀 ⬚ 1≤m≤Mj ∀𝐴∈V≠{𝐴,𝐴}; ∀ 𝑓 ∈F (5) 𝑊+𝑊≤𝑈+𝑈+1 ∀𝑘∈ K ; ∀(𝑖, 𝑗 󰇜∈ N (6) 𝑆𝑀 =1 ⬚ 1≤m≤Mj ∀𝐴∈V≠{𝐴,𝐴} (7) 𝑆 ≤ C (8) 𝑂≤𝑊   ≤𝑈𝐵𝑊·𝑂 ∀𝑘∈K (9) 𝑇𝐿𝐶=𝑊𝐶·𝑂 ⬚ ∈K (10) 𝑋 =𝑆𝑀 ⬚ ∈T ∀𝐴∈V (11) 𝑆+𝑝−1−𝑋·𝑈𝐵𝑆 ≤𝑡≤𝑆+𝑝+1−𝑋·𝑈𝐵𝑆 ∀𝐴∈V; 1≤m≤Mj;∀𝑡∈T (12) 672 𝑤𝑧·𝑤𝑏·𝑋   ⬚ ∈F ⬚ 1≤m≤Mj≤𝑊𝑍 ⬚ ∈N ∀𝑧∈Z; ∀𝑡∈T (13) 𝑆 ≥0 ∀𝐴∈V≠{𝐴} ; 𝑆=0 (14) 𝑋 ∈{0,1} ∀𝐴∈V; 1≤m≤Mj; ∀𝑡∈T (15) 𝑈 ∈{0,1} ∀(𝑖, 𝑗 󰇜∈ N (16) 𝑊 ∈{0,1} ∀𝐴∈V≠{𝐴,𝐴};∀𝑘∈K (17) 𝑆𝑀 ∈{0,1} ∀𝐴∈V; 1≤m≤Mj (18) 𝑂 ∈{0,1} ∀𝑘∈ K (19) The objective function Eq. (1) aims to minimise the total labour cost of workers used in the AAL station per unit of time. Constraints Eq. (2) assure that the precedence relations hold for all pairs of activities (i, j) ∈ E. Constraints Eq. (3) determine the values of variables Uij for each pair of activities (i, j) ∈ N which have no precedence relations, where UBS denotes an upper bound of Sj (could be equal to the cycle time of the assembly line C). Constraints Eq. (4) complement constraints Eq. (3) to provide consistency for variables Uij, that is, for each pair (i, j) ∈ N or Ai starts after Aj is completed (if Uij=1 and Uji=0) or Aj starts after Ai is completed (if Uij=0 and Uji=1) or both are processed simultaneously (if Uij=Uji=0). Constraints Eq. (5) ensure that the profile requirement of the activities in the mode to be performed are fulfilled through the assignment of the necessary workers. Constraints Eq. (6) limit the assignment of each worker to at most one activity at a time. Constraints Eq. (7) ensure that each activity will be performed in one of its modes. Constraint Eq. (8) assures that the last activity is scheduled before the cycle time assigned to the station. In constraints Eq. (9), variables Ok are computed from the values of variables Wjk, where UBW denotes an upper bound of the number of activities a worker can contribute (could be equal to the number of activities n to be performed in the workstation). In constraint Eq. (10), the total labour cost of workers per unit of time is computed. Constraints Eq. (11) to Eq. (13) are mandatory to include the spatial limitations in the workstation zones. Constraints Eq. (11) assure that if an activity Aj is performed using a mode m then the corresponding variable Xjmt is activated to complete the activity at time period t. Otherwise, Xjmt is not activated. Constraints Eq. (12) provide consistency for variables X and S, that is, the completion time t of activity Aj in mode m (if Xjmt=1) must be equal to the starting time of activity Aj (Sj) plus the processing time of j using mode m (pjm). Otherwise (if Xjmt=0), then Sj is limited by an upper bound UBS (could be equal to C). Constraints Eq. (13) ensure that the maximum number of workers per zone is respected. Constraints Eq. (14) and Eq. (15) define the continuous-time and discrete-time variables respectively. Finally, constraints Eq. (16) to Eq. (19) define the binary auxiliary variables. 4. Solution Approach Due to the NP-hard nature of MRCPSP-Z, the difficulty of finding an optimal solution increases exponentially with the problem size. Therefore, this section proposes an ACS and its hybridisation with local search (M-ACS) to optimise the proposed problem. This decision is based on the remarkable success of swarm intelligent algorithms, such as ACO and ACS, in MRCPSP problems (Li and Zhang 2013; Wuliang et al. 2014). In addition, these algorithms can easily incorporate local search procedures due to the inherent use of local heuristics (Dorigo & Stützle 2019). The ACS differs from ACO and other previous ant systems in three main aspects: first, the state transition rule provides a strategy for balancing the exploration of new paths with the knowledge gathered from previous solutions. Second, the global update rule is only applied to the best solution found in the iteration. Third, a local update rule is applied while the ants are building the solution. The aim of this new rule is to diversify the ants' solutions within the iteration by reducing the pheromone concentration in existing scheduling solutions. As a result, previous ants encourage current ants to choose other unexplored paths, making it less likely that several ants will produce identical solutions during an iteration (Dorigo et al., 2006). As ACS is an improvement on ACO, the expected results will therefore be more promising. Since ACS has the advantages of robustness, parallel search characteristics and high solution efficiency (Xu et al. 2023), the search process can easily converge to a local minimum. Therefore, to escape from local optima, the ACS algorithm is combined with a local search phase performed by a Variable Neighbourhood Descent (VND) algorithm, which aims to improve the solution by intensifying the search. This hybridisation is referred to as M-ACS. In addition, to obtain a balance between intensification and diversification of the search space, the local search procedure is only applied to the ant's best solution during each iteration. The remainder of this section introduces the main concepts of the proposed algorithm. Section 4.1 describes the ACS approach in detail and Section 4.2 describes the VND algorithm used in the local search procedure of the M-ACS. M. P. de la Pisa et al. / International Journal of Industrial Engineering Computations 15 (2024) 673 Fig. 1. Title: ACS algorithms workflow Fig. 1. Description: Schematic depiction of ACS and its memetic variant 674 4.1. ACS mechanism for solving MRCPSP-Z The Ant Colony System (ACS) algorithm is a probabilistic metaheuristic inspired by the behaviour of real ants, which find the shortest path when travelling from their nest to a food source. In the ACS algorithm, solutions are constructed in a probabilistic way, considering the attractiveness of the movement and the pheromone trails, which change during the execution of the algorithm. The two main phases of the algorithm are the ant route construction and the pheromone update, which are executed iteratively depending on two global parameters: the ant population (M) and the maximum number of iterations, which is limited by the maximum execution time (time_max). In addition, a minimum slack insertion heuristic is first introduced to start the pheromone trails. The algorithm flowchart of the proposed ACS is shown in Fig. 1. 4.1.1. Individual representation For the MRCPSP-Z, a solution comprises not only the activity sequence but also the activity modes. Thus, to represent an ant solution, a pair of lists I = (LS, LM) is introduced. LS represents a precedence activity list, while LM assigns the activity modes. In order to evaluate solutions, schedules are generated from the information obtained in LS and LM. Two distinct schedule generation schemes can be used in an RCPSP: serial and parallel. SSGS utilises activity incrementation in the stepwise procedure while PSGS utilizes time incrementation. This study adopts SSGS to evaluate solutions. The representation and scheme mentioned above have also been utilized by other authors in MRCPSP, including Zhang (2012), Li and Zhang (2013) and Wuliang et al. (2014). The SSGS therefore selects an activity from the ACS solution according to the sequence in the LS, and resource and zone requirements are determined based on the mode selection LM. Next, the start time of the activity is determined based on the earliest time at which the solution satisfies all MRCPSP-Z constraints (precedence relationship, zone restrictions and maximum number of workers per profile). The SSGS finishes its iteration once J activities are completed and then provides a makespan value, which is defined as the total time required to complete a group of activities. The makespan value is then compared to the cycle time to ultimately determine the solution feasibility. 4.1.2. Fitness function The solution resulting from an evolutionary search must preferably be feasible, meaning that it satisfies all constraints. Nevertheless, the ACS algorithm may commence from infeasible solutions if the makespan value exceeds the total cycle time (C). To explore the infeasible solution space for searching better solutions, it is reasonable that infeasible solutions with smaller makespan values have better fitness values. Taking this consideration into account, a new fitness function, presented in Eq. (20), is proposed in this paper; where PC is a penalty cost coefficient defined as the total cost of using the entire available workforce, and finally mak(S) represents the makespan of the scheduled solution. 𝑓 (𝑆󰇜=𝑇𝐿𝐶(𝑆)+ 𝑃𝐶∙𝑚𝑎𝑥{0 , 𝑚𝑎𝑘(𝑆)−𝐶} (20) 4.1.3. Initial solution and pheromone trails initialisation To initialise the pheromone trails, an initial solution is created using a simple insertion heuristic at the start of the ACS algorithm. A point of primary importance for the MRCPSP-Z is to produce solutions that satisfy the specified cycle time of the workstation. Consequently, the suggested heuristic solely considers the mode with a shorter activity time. In addition, the heuristic prioritizes the insertion of activities with minimum slack during each cycle. The slack of an activity is the difference between its latest start time (LS) and its earliest start time (ES). Note that the calculations are based on the group of unscheduled activities that satisfy the precedence relations, with durations associated to the mode with shorter time. Therefore, the algorithm selects the unscheduled activity with minimum slack and schedules it using a SSGS approach to satisfy all constraints. Most research on ACS algorithms, such as the studies by Reed et al. (2014) and Molina et al. (2020), employed Eq. (21) to determine the initial pheromone value. In this equation, N represents the total number of customers, and L represents the objective function of the solution obtained through the heuristic approach. Similarly, the initial pheromone value is computed by identifying N as the total number of activities. 𝜏=1 𝑁∙𝐿 (21) 1 As ← ActivityList() “Unassigned activities”; 2 While (As ≠ 0) do: 3 For each activities a of As do: 4 mode← ShorterTimeDuration (a) 5 Slacka,mode← Calculate_slack (a, mode, S), 6 (best_act, best_mode) ← StoreBest(Slacka,mode) 7 EndFor 8 S ← InsertActivity(best_act, best_mode), As ← RemoveActivity(best_act) 9 EndWhile 10 Return (S) Fig. 2. Title: Algorithm 2: Minimum slack insertion heuristic Fig. 2. Description: Illustration presenting the programming code of the Minimum slack insertion heuristic algorithm M. P. de la Pisa et al. / International Journal of Industrial Engineering Computations 15 (2024) 675 4.1.4. Solution construction Following the scheme considered by Li and Zhang (2013), two different decisions are made by an ant in solution searching; firstly, the selection of an activity j at the position i in the precedence activity list (LS); secondly, the selection of the execution mode m for the activity j at the position i. To facilitate these decisions, two types of pheromones (τij and τijm), two types of attractiveness (ηij and ηijm) and two types of probabilities (pij and pijm) are respectively considered. 1 Initialize schedule (LS, LM); 2 Initialize non-yet-scheduled-activity list Aj, j=1,2,…,N; 3 For all positions i of LS do: 4 J(i)←Find_Feasible_Insertion_Activities(Aj); 5 q←Select_Random_Number(); 6 For all activities j of J(i) do: 7 mode←Min_Duration(j); 8 ηi,j ←Min_slack(LS, LM,mode); 9 pi,j ←Calculate_Probabilities(ηi,j, τ(N,N)); 10 EndFor 11 If (q<= q0) then: 12 t ←Maximum_Value(pi,j); 13 Else: 14 t ←Roulette_Wheel_Selection (pi,j); 15 EndIf 16 LS ← Insert(i, t); Aj ← Remove_Activity(t); 17 q2←SelectRandomNumber(); 18 For all modes m of t do: 19 ηi,t,m ←Min_Difference_Cost(LS, LM); 20 pi,t,m ←Calculate_Probabilities( ηi,t,m, τ(N,N,MODES)); 21 EndFor 22 If (q2<= q0) then: 23 m←Maximum_Value(pi,t,m); 24 Else: 25 m ←Roulette_Wheel_Selection (pi,t,m); 26 EndIf 27 LM ← Insert(i, mode); 28 EndFor 29 Return (LS, LM); Fig. 3. Title: Algorithm 3: Ant Solution Construction Procedure Fig. 3. Description: Illustration presenting the programming code of the Ant Solution Construction Procedure In the ACS algorithm, ants travel from one activity to another activity to construct a solution. During each construction step, ants firstly select an unscheduled activity to be inserted into the next position of the LS. This is done using a pseudo-random proportional rule. If a random number, q, which is uniformly distributed over [0.100], is less than q0, the best activity is selected based on its pheromone and attractiveness. For this purpose, Eq. (22) is utilised where pij represents the probability of selecting an activity j in position i. Otherwise, the activity is selected by a fitness proportionate selection, also known as roulette wheel selection, according to the probability distribution provided in Eq. (22). Probability pij incorporates two separate components; the pheromone level during selection (i,j) denoted as τij, and attractiveness (ηij). J(i) denotes the groups of activities with feasible insertions in position i. 𝑝=⎩ ⎪ ⎨ ⎪ ⎧ 𝜏∙𝜂 ∑(𝜏)∙(𝜂) ∈() , 𝑖𝑓 𝑗 ∈ 𝐽 (𝑖) ⬚ 0, 𝑜𝑡ℎ𝑒𝑟𝑤𝑖𝑠𝑒 (22) The attractiveness of the move in this decision is based on the priority given to the activity with the smaller total slack, following the same criterion used in the construction heuristic proposed in Section 4.1.3. The slack is calculated for every feasible insertion associating activity durations to the mode with a shorter time and considering the selected modes for the scheduled activities i. This measure was also utilised by Zhang (2012) and Li and Zhang (2013) in their corresponding studies and can be computed with Eq. (23). η=max ∈()(LS−ES) −LS−ES+ 1 (23) 682 Table 5 Results for Set60 and Set90 instances Instance name Number of tasks Number of resources Number of proficiency levels Number of profiles Total modes Maximum zones occupation Time elapsed (seconds) ACS M-ACS Min TLC Average TLC Min TLC Average TLC Rel. dev. from Min TLC ACS Time used in LS (%) Set_60.R3.L2_1 60 3 2 6 211 4 1080 203 203 203 (=) 203 (=) 0,0% 43% Set_60.R3.L2_2 60 3 2 6 233 4 1080 277 277 272 (<) 272 (<) -1,8% 75% Set_60.R3.L2_3 60 3 2 6 182 5 1080 235 235 235 (=) 235 (=) 0,0% 39% Set_60.R3.L2_4 60 3 2 6 182 5 1080 234 234 234 (=) 234 (=) 0,0% 43% Set_60.R3.L3_1 60 3 3 9 333 4 1620 269,5 270,7 266,5 (<) 268,6 (<) -1,1% 59% Set_60.R3.L3_2 60 3 3 9 306 4 1620 175,5 175,5 175,5 (=) 175,5 (=) 0,0% 66% Set_60.R3.L3_3 60 3 3 9 339 5 1620 236 236 236 (=) 236 (=) 0,0% 49% Set_60.R3.L3_4 60 3 3 9 319 5 1620 225 225 221 (<) 224,2 (<) -1,8% 48% Set_60.R4.L2_1 60 4 2 8 189 4 1440 184 184 184 (=) 184 (=) 0,0% 42% Set_60.R4.L2_2 60 4 2 8 182 4 1440 286 286 286 (=) 286 (=) 0,0% 42% Set_60.R4.L2_3 60 4 2 8 203 5 1440 282 282 282 (=) 282 (=) 0,0% 43% Set_60.R4.L2_4 60 4 2 8 192 5 1440 279 279 279 (=) 279 (=) 0,0% 44% Set_60.R4.L3_1 60 4 3 12 319 4 2160 251,5 251,5 251,5 (=) 251,5 (=) 0,0% 50% Set_60.R4.L3_2 60 4 3 12 313 4 2160 268,5 269,4 264,5 (<) 265,3 (<) -1,5% 71% Set_60.R4.L3_3 60 4 3 12 320 5 2160 283,5 288,4 283,5 (=) 283,5 (<) 0,0% 80% Set_60.R4.L3_4 60 4 3 12 352 5 2160 277 277 275 (<) 276 (<) -0,7% 73% Set_90.R3.L2_1 90 3 2 6 294 4 2430 254 254 254 (=) 254 (=) 0,0% 43% Set_90.R3.L2_2 90 3 2 6 272 4 2430 255 255 255 (=) 255 (=) 0,0% 43% Set_90.R3.L2_3 90 3 2 6 292 5 2430 212 212 212 (=) 212 (=) 0,0% 42% Set_90.R3.L2_4 90 3 2 6 269 5 2430 176 176 176 (=) 176 (=) 0,0% 43% Set_90.R3.L3_1 90 3 3 9 445 4 3645 182,5 182,5 182,5 (=) 182,5 (=) 0,0% 71% Set_90.R3.L3_2 90 3 3 9 448 4 3645 174,5 174,5 174,5 (=) 174,5 (=) 0,0% 48% Set_90.R3.L3_3 90 3 3 9 557 5 3645 270,5 272,5 270,5 (=) 272,3 (<) 0,0% 72% Set_90.R3.L3_4 90 3 3 9 545 5 3645 220 220 220 (=) 220 (=) 0,0% 51% Set_90.R4.L2_1 90 4 2 8 324 4 3240 289 289,4 289 (=) 290,6 (>) 0,0% 43% Set_90.R4.L2_2 90 4 2 8 295 4 3240 336 336 336 (=) 336 (=) 0,0% 72% Set_90.R4.L2_3 90 4 2 8 297 5 3240 299 299 299 (=) 299 (=) 0,0% 42% Set_90.R4.L2_4 90 4 2 8 307 5 3240 246 247,8 246 (=) 247,2 (<) 0,0% 42% Set_90.R4.L3_1 90 4 3 12 515 4 4860 260 260 260 (=) 260 (=) 0,0% 50% Set_90.R4.L3_2 90 4 3 12 479 4 4860 246,5 246,5 244,5 (<) 245,3 (<) -0,8% 73% Set_90.R4.L3_3 90 4 3 12 544 5 4860 323,5 323,7 323 (<) 324 (>) -0,2% 53% Set_90.R4.L3_4 90 4 3 12 466 5 4860 245,5 246,4 247 (>) 247 (>) 0,6% 46% Average values 248,64 249,03 248,05 (<) 248,47 (<) -0,23% 53,14% 6. Conclusions This paper introduces the MRCPSP-Z to respond to the particularities of an AAL workstation, where the main objective is to minimise the total labour cost given a fixed cycle time per station. The problem has been defined as a variant of the MRCPSP, considering additional workers for each activity, different workers’ proficiency and spatial constraints in the work zones. First, the problem was developed as a MILP model. Then, since the problem is NP-hard, two algorithms based on the Ant Colony System were developed, the standard ACS and a memetic ACS that includes a VND algorithm for the local search phase. Both algorithms considered two different types of pheromones, two types of heuristic information and SSGS for solution representation. Furthermore, a resource peak reduction mechanism was implemented to find solutions that SSGS cannot reach. As the problem has not been addressed in previous research, computational tests were performed using new benchmark instances adapted to the characteristics of the presented MRCPSP-Z. For small size sets, ACS and M-ACS solutions were compared with exact method solutions. The results show a high percentage of optimal solutions found and a reduced relative average deviation, justifying the effectiveness of the proposed solution approaches. Medium and large size sets were also solved to demonstrate the efficiency and robustness of the two algorithms, concluding with a slightly better performance of M-ACS compared to ACS. After evaluating the effectiveness of the VND, the exploration phase results to be more efficient than the intensification phase for this problem where cost is the objective. This is due to the difficulty in finding neighbours solutions that could lead to a reduction of TLC. Finally, this paper fills the lack of existing applications in the AAL literature that consider real factory characteristics, providing promising solutions in reasonable CPU time. The results are also relevant for researchers, as they present a new problem that has not been addressed before. Further research could focus on developing new solution approaches to solve the MRCPSP-Z. The problem could be extended with a multi-objective approach to include additional objectives relevant to the industry, or to include multi-skilled workers and stochastic processing times that are characteristic of other industries. M. P. de la Pisa et al. / International Journal of Industrial Engineering Computations 15 (2024) 683 Data Availability Statement The data that support the findings of this study are openly available in [“figshare”] at http://doi.org/10.6084/m9.figshare.21400035. References Afshar, M. R., Shahhosseini, V., & Sebt, M. H. (2022). A genetic algorithm with a new local search method for solving the multimode resource-constrained project scheduling problem. International Journal of Construction Management, 22(3), 357-365. Ahmadpour, S., & Ghezavati, V. (2019). Modeling and solving multi-skilled resource-constrained project scheduling problem with calendars in fuzzy condition. Journal of Industrial Engineering International, 15(1), 179-197. Arkhipov, D., Battaïa, O., Cegarra, J., & Lazarev, A. (2018). Operator assignment problem in aircraft assembly lines: a new planning approach taking into account economic and ergonomic constraints. Procedia CIRP, 76, 63-66. Baradaran, S., Ghomi, S. F., Ranjbar, M., & Hashemin, S. S. (2012). Multi-mode renewable resource-constrained allocation in PERT networks. Applied Soft Computing, 12(1), 82-90. Blazewicz, J., Lenstra, J. K., & Kan, A. R. (1983). Scheduling subject to resource constraints: classification and complexity. Discrete applied mathematics, 5(1), 11-24. Borreguero, T. (2019). Scheduling with limited resources along the aeronautical supply chain: from parts manufacturing plants to final assembly lines. PhD diss., E.T.S.I. Industriales (UPM). Borreguero, T., García, A., & Ortega, M. (2015). Scheduling in the aeronautical industry using a mixed integer linear problem formulation. Procedia engineering,132, 982-989. Cheng, H., & Chu, X. (2012). Task assignment with multiskilled employees and multiple modes for product development projects. The International Journal of Advanced Manufacturing Technology, 61(1), 391-403. Chiang, C. W., & Huang, Y. Q. (2012). Multi-mode resource-constrained project scheduling by ant colony optimization with a dynamic tournament strategy. In 2012 Third international conference on innovations in bio-inspired computing and applications (pp. 110-115). IEEE. Correia, I., Lourenço, L. L. & Saldanha-da-Gama, F. (2012). Project scheduling with flexible resources: formulation and inequalities. OR Spectrum, 34, 635–663. Dolgui, A., Kovalev, S., Kovalyov, M. Y., Malyutin, S., & Soukhal, A. (2018). Optimal workforce assignment to operations of a paced assembly line. European Journal of Operational Research, 264(1), 200-211. Dorigo, M., & Stützle, T. (2019). Ant colony optimization: overview and recent advances. Handbook of metaheuristics, 311351. Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization. IEEE computational intelligence magazine, 1(4), 28-39. Duarte, A., Mladenovic, N., Sánchez-Oro, J., & Todosijević, R. (2018). Variable neighborhood descent. In Handbook of Heuristics, Springer International Publishing, 341-367. Heike, G., Ramulu, M., Sorenson, E., Shanahan, P., & Moinzadeh, K. (2001). Mixed model assembly alternatives for lowvolume manufacturing: the case of the aerospace industry. International Journal of Production Economics, 72(2), 103120. Kadrou, Y., & Najid, N. M. (2006). A new heuristic to solve RCPSP with multiple execution modes and Multi-Skilled Labor. In The Proceedings of the Multiconference on Computational Engineering in Systems Applications (Vol. 2, pp. 13021309). IEEE. Khalilzadeh, M. (2015). A honey bee swarm optimization algorithm for minimizing the total costs of resources in MRCPSP. Indian Journal of Science and Technology, 8(11). Kolisch, R., & A. Sprecher. (1997). PSPLIB-a project scheduling problem library: OR software-ORSEP operations research software exchange program. European journal of operational research, 96(1), 205-216. Li, C., Wang, F., & Chung, T. (2024). Multi-mode multi-skill resource-constrained project scheduling problem with differentiated professional capabilities. Journal of Project Management, 9(1), 27-44. Li, H., & Zhang, H. (2013). Ant colony optimization-based multi-mode scheduling under renewable and non-renewable resource constraints. Automation in construction, 35, 431-438. Miralles, C., Garcia-Sabater, J. P., Andrés, C., & Cardos, M. (2007). Advantages of Assembly Lines in Sheltered Work Centres for Disabled. A Case Study. International Journal of Production Research, 110(2), 187–197. Mladenović, N., & Hansen, P. (1997). Variable neighborhood search. Computers and operations research, 24(11), 10971100. Molina, J. C., Salmeron, J. L., & Eguia, I. (2020). An ACS-based memetic algorithm for the heterogeneous vehicle routing problem with time windows. Expert Systems with Applications, 157, 113379. Moscato, P. (1989). On evolution, search, optimization, genetic algorithms and martial arts: Towards memetic algorithms. Caltech concurrent computation program, C3P Report, 826, 1989. 684 Pellerin, R., Perrier, N., & Berthaut, F. (2020). A survey of hybrid metaheuristics for the resource-constrained project scheduling problem. European Journal of Operational Research, 280(2), 395-416. Povéda, G., Alvarez, N., & Artigues, C. (2023). Partially Preemptive Multi Skill/Mode Resource-Constrained Project Scheduling with Generalized Precedence Relations and Calendars. In 29th International Conference on Principles and Practice of Constraint Programming (CP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 280, pp. 31:1-31:21 Reed, M., Yiannakou, A., & Evering, R. (2014). An ant colony algorithm for the multi-compartment vehicle routing problem. Applied Soft Computing, 15, 169-176. Ritt, M., Costa, A. M., & Miralles, C. (2016). The assembly line worker assignment and balancing problem with stochastic worker availability. International Journal of Production Research, 54(3), 907-922. Russell, A., & Taghipour, S. (2019). Multi-objective optimization of complex scheduling problems in low-volume lowvariety production systems. International Journal of Production Economics, 208, 1-16. Shahnazari-Shahrezaei, P., Zabihi, S., & Kia, R. (2017). Solving a multi-objective mathematical model for a multi-skilled project scheduling problem by particle swarm optimization and differential evolution algorithms. Industrial Engineering and Management Systems, 16(3), 288-306. Shan, M., Hong, Q., & Juan, W. (2007). Multi-mode multi-project scheduling problem for mould production in MC enterprise. In 2007 International Conference on Wireless Communications, Networking and Mobile Computing (pp. 5316-5320). IEEE. Shen, H., & Li, X. (2013). Cooperative discrete particle swarms for multi-mode resource-constrained projects. In Proceedings of the 2013 IEEE 17th International Conference on Computer Supported Cooperative Work in Design (CSCWD) (pp. 3136). IEEE. Taguchi, G., Chowdhury, S., & Wu. Y. (2005). Taguchi’s Engineering Quality Handbook, John Willey and Sons. Inc, Hoboken, New Jersey. Van Peteghem, V., & Vanhoucke, M. (2014). An experimental investigation of metaheuristics for the multi-mode resourceconstrained project scheduling problem on new dataset instances. European Journal of Operational Research, 235(1), 6272. Vanhoucke, M., Coelho, J., Debels, D., Maenhout, B., & Tavares, L. V. (2008). An evaluation of the adequacy of project network generators with systematically sampled networks. European Journal of Operational Research, 187(2), 511-524. Vinay, V. P., & Sridharan, R. (2013). Taguchi method for parameter design in ACO algorithm for distribution–allocation in a two-stage supply chain. The International Journal of Advanced Manufacturing Technology, 64(9), 1333-1343. Wuliang, P., Min, H., & Yongping, H. (2014). An improved ant algorithm for Multi-mode Resource Constrained Project Scheduling Problem. RAIRO-Operations Research, 48(4), 595-614. Xu, G., Lin, H., Cheng, Y., & Li, S. (2023). An Improved Ant Colony Optimization for Solving Task Scheduling Problem in Radar Signal Processing System. Journal of Signal Processing Systems, 1-18. Zhang, H. (2012). Ant colony optimization for multimode resource-constrained project scheduling. Journal of Management in Engineering, 28(2), 150-159. © 2024 by the authors; licensee Growing Science, Canada. This is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC-BY) license (http://creativecommons.org/licenses/by/4.0/).