WorksComputer Science
A batch production scheduling problem in a reconfigurable hybrid manufacturing-remanufacturing system
Abstract
In recent years, remanufacturing of End-of-Life (EOL) products has been adopted by manufacturing sectors as a competent practice to enhance their sustainability and market share. Due to the mass customization of products and high volatility of market, processing of new products and remanufacturing of EOLs in the same shared facility, namely Hybrid Manufacturing-Remanufacturing System (HMRS), is a mean to keep such production efficient. Accordingly, customized production capabilities are required to increase flexibility, which can be effectively provided under the Reconfigurable Manufacturing System (RMS) paradigm. Despite the advantages of utilizing RMS technologies in HMRSs, production management of such systems suffers excessive complexity. Hence, this study concentrates on the production scheduling of an HMRS consisting of non-identical parallel reconfigurable machines where the orders can be grouped into batches. In this regard, Mixed-Integer Linear Programming (MILP) and Constraint Programming (CP) models are devised to formulate the problem. Furthermore, a computationally efficient solution method is developed based on a Logic-based Benders Decomposition (LBBD) approach. The warm start technique is also implemented by providing a decent initial solution to the MILP model. Computational experiments attest to the LBBD method's superiority over the MILP, CP, and warm-started MILP models by obtaining an average gap of about 2%, besides it yields actionable managerial insights for scheduling in HMRSs.
Introduction
In recent decades, the staggering global population growth, globalization, and digitalization have led to a tremendous demand surge in manufactured products. If the current consumption rate under the conventional linear manufacturing paradigm (i.e., produce, consume, dispose) is maintained, 2.3 times the Earth's resources are required by 2050 to meet the demand [1]. As a result, policymakers, manufacturers, and academia have strictly pursued closing material loops under the concept of circular economy [2, 3].
Remanufacturing has been recognized as an effective approach in the circular economy to achieve sustainability [4] and enhance resiliency against unprecedented disruptions in the supply chain like the COVID-19 pandemic [5]. It is defined as comprehensive processes by which an end-of-life (EOL) product is brought to the like-new state with quality and performance equal to or better than a new product [6, 7].
In comparison with new products manufacturing, remanufacturing enjoys cost savings (up to 50%), material savings (up to 70%), energy savings (up to 60%), CO₂ emission reduction (up to 87%), and lower prices (up to 40%) with a decent profit margin (around 20%) [8, 9]. Nevertheless, remanufacturing is an emerging market far from reaching its full potential. Based on a study performed by the European Remanufacturing Network (ERN), the annual value of remanufactured products in Europe was estimated at €30 billion in 2016, possible to reach €100 billion in 2030 [10]. Accordingly, different manufacturing sectors like aerospace, automotive, electrical, medical device, machinery, and furniture have adopted remanufacturing to enhance their market share and environmentally responsible practices [11, 12].
Manufacturers have practiced two approaches regarding the implementation of remanufacturing: 1) performing manufacturing of new products from raw materials and remanufacturing of EOL products in separated dedicated facilities; or 2) performing the both utilizing the same shared facility, namely the hybrid manufacturing-remanufacturing system (HMRS) [13]. The former approach is effective if a large quantity of EOL products is ensured. However, when the quantity of EOL products is limited, or their return timing is unknown (e.g., as in make-to-order environments), it leads to significant underutilization. In these situations, HMRSs provide the most promising alternative [13, 14]. Processing both raw materials and EOL parts in an HMRS may necessitate different production capabilities. In this regard, Reconfigurable Manufacturing Systems (RMSs) best fit HMRSs [15, 16, 17] since RMSs can quickly and cost-effectively adjust their structure, hardware, and software components to provide customized production capabilities [18, 19]. In RMSs, various configurations with different production capabilities can be attained by adding, removing, or modifying the modules of machines. For instance, Figure 1(a) shows a robotic additive-subtractive machine located at Czech Technical University in Prague [20] that its arm's head (Figure 1(b)) can be changed automatically. As a result, different additive and subtractive capabilities can be implemented.

Figure 1. (a) Robot arm. (b) Different heads. A hybrid robotic additive-subtractive machine.
Despite the advantages of utilizing RMS technologies in HMRSs, production management of such systems encounters higher complexity than conventional systems due to the additional reconfiguration decisions. In this regard, this study concentrates on the production scheduling of an HMRS consisting of non-identical parallel reconfigurable machines (stations or production cells). Moreover, manufacturing and/or remanufacturing orders can be grouped into capacity-constrained batches to save machine setup times. Hence, the serial-batch processing of orders is incorporated, where the processing time of a batch is the total processing time of its assigned orders. Accordingly, the decisions regarding (i) the assignment of the orders to the eligible machine-configuration combinations based on the manufacturing and remanufacturing requirements, (ii) batching the assigned orders to each machine, and (iii) the scheduling of the batches on the machines should be simultaneously made to minimize the makespan.
First, the problem is formulated as a Mixed-Integer Linear Programming (MILP) model and its Constraint Programming (CP) counterpart. Furthermore, an efficient solution method is developed based on a Logic-based Benders Decomposition (LBBD) approach. Additionally, to enhance the performance of the MILP model, the warm start technique is implemented by providing an initial solution using a two-step procedure consisting of mathematical models. Finally, through computational experiments, the performance of the developed MILP, CP, LBBD, and warm-started MILP (WMLIP) are compared, and key managerial insights are extracted as well.
The rest of this paper is presented as follows. § 2 briefly reviews studies regarding production scheduling in HMRSs and RMSs, and emphasizes the novel aspects of this study. In § 3, the investigated scheduling problem in an HMRS is elaborated. § 4 provides the MILP model and its equivalent CP model. The WMILP and the LBBD approach are expressed in § 5. § 6 focuses on evaluating the proposed solution methods, in addition to performing relevant sensitivity analysis on the impactful parameters of the problem. Finally, § 8 summarizes the study and proposes some directions for further research on this topic.
Literature review
In this section, the related scheduling problems in two areas, including HMRSs and RMSs, are briefly reviewed, and at the end, the contributions of this study are accentuated.
Scheduling in hybrid manufacturing-remanufacturing systems
The literature regarding the scheduling in dedicated remanufacturing systems is well-established. Some studies have only focused on the disassembly stage (e.g., Ehm [21]) or just processing of EOL products (e.g., Shi et al. [22]), while others considered scheduling decisions related to disassembly, reprocessing, and assembly in an integrated manner (e.g., Wang et al. [23]; Guo et al. [24]). On the contrary, there is a few research regarding scheduling in hybrid manufacturing-remanufacturing systems.
Regarding a stable demand pattern over the long term, Tang and Teunter [25] studied a multi-product economic lot scheduling problem in which, for each product, there is one lot for manufacturing and one lot for remanufacturing. Considering a common cycle policy, they provided an MILP-based algorithm to determine the optimal lot size and their sequence, minimizing the sum of the inventory holding cost and sequence-independent setup cost. Due to the impracticality of this algorithm in large-sized problems, Teunter, Tang and Kaparis [26] later developed a heuristic method capable of finding near-optimal solutions. Zanoni et al. [27] further extended this problem by relaxing the common cycle restriction and the presence of only one lot for (re)manufacturing, and presented a basic period policy to solve it. Aminipour, Bahroun and Hariga [28] delved into a cyclic scheduling problem with a cyclic pattern in each product demand. The demand can be fulfilled by both manufactured and remanufactured products. The cycle is discretized into multiple periods in which only the manufacturing or remanufacturing of one product can be performed. They proposed an MILP model for the problem to minimize the sum of manufacturing and remanufacturing setup cost, and holding cost for the EOL items, manufactured and remanufactured products.
Concerning a variable demand pattern over short- or mid-term, an integrated lot-sizing and scheduling problem (ILSP) was explored by Giglio et al. [29] in a job shop environment with compressible processing times. They assumed that manufactured and remanufactured products are the same in satisfying the demand. Moreover, the processing routes for manufacturing and remanufacturing products are the same, with different nominal processing times. They proposed a Mixed-Integer programming (MIP) model and a relax-and-fix heuristic for the problem considering the total cost of energy, back-logging, setup, production, and EOL and serviceable products inventory. Later, Roshani et al. [30] considered similar settings for an ILSP problem on a single machine problem besides the incorporation of sequence-dependent setup times and costs for both manufacturing and remanufacturing of products. They presented an MILP model, a relax-and-fix heuristic, and a grey wolf optimization algorithm to tackle the complexity of the problem. Torkaman et al. [31] studied an ILSP in a flow shop environment with sequence-dependent setup time/cost between two different types of products. Moreover, different quality levels for EOL products influence the processing times for remanufacturing. In addition, no setup was considered between the manufacturing and remanufacturing a specific product. They developed an MIP, a rolling horizon heuristic, and a hybrid metaheuristic to solve the problem, optimizing the total cost of inventory (EOL product, work in progress, and final products), setup, manufacturing, and remanufacturing.
Scheduling in reconfigurable manufacturing systems
The Reconfigurable Manufacturing System, as a novel manufacturing paradigm, has demonstrated a significant performance in confronting current manufacturing challenges [32, 33]. It has a customized flexibility that enables it to adjust to production requirements efficiently [18, 19]. So far, different problems arising from the management of RMSs, like system design, process planning, production planning, and production scheduling, have been investigated [19, 33]. Nevertheless, research related to RMS scheduling is still in its early stages.
In RMS scheduling, besides scheduling jobs on machines, decisions regarding the reconfigurations of the system and machines during the planning horizon are necessary. Accordingly, system-level reconfiguration (i.e., adding, removing, or rearranging machines and equipment) has been discovered in cellular manufacturing [34], flow line [35], flexible transfer line [36], and assembly line [37]. In addition, machine-level reconfiguration (i.e., adding, removing, or modifying modules of machines) has been incorporated in the scheduling of single machine [38], parallel machine [39], flow shop [40, 41], job shop [42, 43], flexible job shop [44, 45] environments. Other production decisions have also been integrated into RMS scheduling, including process planning [46, 47], workforce planning [39, 42], lot-sizing [48, 49], outsourcing [40], and machine module allocation [50].
Due to the inclusion of the above-mentioned decisions in RMS scheduling problems, they bear higher complexity than conventional production scheduling problems. As a result, in addition to mathematical models, different solution approaches have been developed to confront these complexities, including CP [42], metaheuristic (e.g., memetic algorithm [38], multi-objective particle swarm optimization algorithm [35], differential evolution algorithm [44], equilibrium optimizer [51], Non-dominated Sorting Genetic Algorithm III [46], genetic algorithm [50], and multi-start evolutionary local search [43]), heuristic [47], machine learning (e.g., deep reinforced learning [52]) and hybrid methods (e.g., a combination of MILP and CP models [39], and a combination of genetic algorithm and MILP model [49]).
Contributions of this study
Although Aljuneidi and Bulgak [16] and Aljuneidi and Bulgak [17] investigated the system-level reconfigurations in HMRSs at tactical production decision-making (i.e., production planning), no research has studied the machine-level reconfigurations in operational decision-making (i.e., production scheduling) of HMRSs. Moreover, despite the benefit of batch processing in many practical situations, like additive manufacturing in reducing unnecessary setups [53], it has been explored in neither HMRS scheduling nor RMS scheduling problems. To fill these gaps, this study provides the following contributions to the literature:
Focusing on the scheduling of an HMRS benefiting from RMS concepts to facilitate the inclusion of manufacturing and remanufacturing in a shared production system. In this regard, the machines (stations or cells) can be reconfigured to provide the required production capabilities as required.
Considering the possibility of processing manufacturing or remanufacturing orders in separate batches, or combining them in a same batch, for scheduling in a reconfigurable HMRS.
Developing novel MILP and CP models to formally formulate the investigated problem.
Devising an efficient LBBD to confront the complexity of the problem. Accordingly, the master problem deals with assigning orders to machine-configuration combinations, and sub-problems involve batching and scheduling orders for each machine.
Employing the warm start technique to boost the performance of the developed MILP model (namely WMILP) using a two-step procedure consisting of mathematical models.
6). Performing comprehensive computational experiments to assess the performance of the proposed MILP model, CP model, LBBD method, and WMILP, as well as providing relevant managerial insights.
Contributions 1 and 2 refer to the knowledge this paper generates on the scheduling of HMRSs. We explicate how the results advance the relevant literature and extend existing knowledge of HMRS. Contributions 3-6 refer to innovative methodologies, including the MILP model, CP model, LBBD method, and WMILP. For example, the underlying challenge of the LBBD is that the execution of the method might be halted due to time and memory limitations and the presence of many inactive cuts, which result in a large MP with a high solution time. As investigated by Rahmaniani et al. [54], nearly 90% of the overall running time in these types of decomposition methods is used for solving the MP. In the present research, our decomposition strategy specifically focuses on finding a way to partition the problem effectively into MP and SPs. This involves developing new properties that account for problem-specific characteristics and exploring alternative ways to divide the LBBD into MP and SPs. Another significant contribution of the LBBD to overcome such a challenge is to find a tight lower bound (LB) that is a relaxation of the SPs.
We focus on a situation where the aforementioned exact methods can be more suitable than metaheuristics for scheduling HMRSs. A reason behind this intuition is that metaheuristics, while capable of exploring a larger solution space, often do so at the cost of greater variability (e.g., see [43] for the case of RMSs). Accordingly, the study is limited to computational experiments involving the MILP model, CP model, LBBD method, and WMILP.
Problem description
We first present the notation for the scheduling problem, followed by an explanation of the components of a hybrid manufacturing-remanufacturing system. Table 1 summarizes the key notation and symbols, with detailed definitions provided throughout the section. The section elaborates on the scheduling problem regarding a hybrid manufacturing-remanufacturing system comprising a set of parallel non-identical reconfigurable machines (stations or production cells) denoted by . The set of orders is represented by . More precisely, two types of orders are received in the system. Manufacturing orders that are produced by raw materials, and remanufacturing orders that require the processing of EOL products. We denote as disjoint sets and the sets of manufacturing and remanufacturing orders, respectively. As a result, different production capabilities are necessary to meet the demands of this shared system provided by the reconfigurable machines. Assume machine with configuration shows a machine-configuration combination. Then, each machine configuration may satisfy the requirements of a predefined number of manufacturing or remanufacturing orders (), which is called the eligible configuration (). On the other hand, at least one eligible machine-configuration combination is capable of processing an order. In order to save setup times, it is possible to group parts into batches under specific machine configurations. In this case, the setup time () is shared by the orders of a particular batch . However, each machine has a limited processing area capacity of and height of that constrain the inclusion of orders in a batch. The other assumptions of this problem are listed as follows.
| Sets and indices | |
| Set of manufacturing orders | |
| Set of remanufacturing orders | |
| Set of orders, | |
| Set of batches | |
| Set of machines | |
| Set of configurations belongs to machine | |
| Index of order | |
| Index of batch | |
| Index of machine | |
| Index of configuration; represents the initial configuration | |
| Parameters | |
| Order area: the area occupied by order in a batch | |
| Order height: the height of order | |
| Machine processing area: the maximum area provided by machine for batch processing | |
| Machine processing height: the maximum acceptable height of an order to be processed by machine | |
| Order processing time: the time required to process order by configuration of machine | |
| Batch setup time on machine with configuration | |
| Batching limit: 1 if at most one order can be placed within a batch on machine with configuration ; 0, otherwise | |
| 1 if configuration of machine is eligible to process order | |
| The time needed to reconfigure machine from configuration to | |
| A large positive number |
Table 1. Important notation and symbols
The set of orders and their requirements are known and available at the beginning of the planning horizon.
The processing time () of an order is deterministic and dependent on the assigned machine-configuration combination.
Based on the requirements of orders, a batch on a specific configuration of a machine can include only manufacturing orders from set , only remanufacturing orders from set , or both manufacturing and remanufacturing orders.
Each order height and the total area occupied by the orders of a batch are denoted by and , respectively, and cannot surpass the processing height and area limits of its related machine .
The processing time of a batch is the total processing times of its assigned orders following the definition of serial-batch processing.
Each batch is performed by a configuration of its corresponding machine, and its setup time depends on the assigned configuration.
At any moment, at most, one batch can be processed on a machine.
During the processing of a batch, it cannot be interrupted, and any order cannot be added or removed from it.
If the selected configurations of two adjacent batches on a machine are different, a reconfiguration time of is required depending on the former and latter configurations of and . Moreover, the reconfiguration times follow the triangle inequality, i.e, .
During a reconfiguration, no batch can be processed on the corresponding machine.
Variables
| 1 if order is assigned to batch of machine being processed with configuration ; 0, otherwise | |
| 1 if batch of machine is formed and being processed with configuration ; 0, otherwise | |
| 1 if batches with configuration are processed after those with configuration ; 0, otherwise | |
| 1 if configuration of machine is utilized; 0, otherwise | |
| Configuration duration: the time required to process batches with configuration on machine including their setup times | |
| Configuration completion time: the completion time of batches with configuration on machine | |
| The maximum completion time of all configurations or batches (i.e., makespan) |
The problem seeks simultaneous decision-making concerning (i) the assignment of each order to an eligible machine-configuration respecting the height and area limits, (ii) batching the orders assigned to each machine-configuration respecting the area limit, and (iii) the scheduling of the batches on the machines to minimize the makespan. Figure 2 illustrates the problem by a simple example. As shown in the figure, there are 2 reconfigurable machines in the system, each with 3 configurations. The assignment of orders to machineconfigurations, batching of orders on machines, and their scheduling are also presented. For instance, remanufacturing order and manufacturing order are assigned to Configuration and Configuration of Machine, respectively. Manufacturing orders , , and are included in Batch of Machine, and remanufacturing orders and on Batch Machine. A reconfiguration is required between the processing of Batch and Batch of Machine from Configuration to Configuration (-). Moreover, due to the similar processing requirements of manufacturing order and remanufacturing order , it is possible to process them within Batch of Machine.

Figure 2. A simple illustrative example of the reconfigurable HMRS scheduling problem.
Problem formulation
In this section, first, two properties of an optimal solution to the reconfigurable HMRS scheduling problem are introduced. Afterward, the notation of the reconfigurable HMRS scheduling problem is presented. Subsequently, the MILP and CP models are extended.
Properties of an optimal solution to the problem
Prior to presenting the MILP model, we first introduce two properties of an optimal solution to the reconfigurable HMRS scheduling problem. Employing them in the modeling leads to a reduction in the solution space and enhances its performance accordingly. These properties are a modification of the ones provided by Vahedi-Nouri et al. [39] for workforce planning and scheduling in a parallel machine environment consisting of reconfigurable machines.
Property I. In the case of the reconfigurable HMRS scheduling problem, there is always an optimal solution where, on every machine, all the batches with an identical configuration are processed successively.
Proof. Two following cases are needed to be explored in this regard:
For machine in an optimal solution in which the completion time of its last batch is equal to : following the proof by contraction method, assume represents the optimal schedule on machine in which Property I is not held. Thus, at least one batch can be found processed apart from other batches with the same configuration on machine . Figure 3(a) demonstrates , in which denotes the reconfiguration

Figure 3. Three schedules of a machine demonstrating properties of an optimal solution
time, the batch on the position of , and each color signifies a configuration of machine . The makespan of () is determined by Equations (1) and (2), where is the first employed configuration in , and is the processing time of a batch including its setup time.
Considering the fact that no precedence relationship exists between orders, a feasible solution can be reached by inserting just after without any needs of reconfiguration. This solution, referred to as , is shown in Figure 3(b). Hence, can be calculated by Equation (3):
Comparing the makespan of the two schedules, it is evident that . Hence, the makespan of is lower than of , which is in contradiction to the assumption. In the same way, if more than one batch does not observe Property I, this difference can be even enlarged.
2) For machine in an optimal solution in which the completion time of its last batch is less than : assume that Figure 3(a) indicates this case. Thus, by processing just after (as shown in Figure 3(b)), is decreased. Hence, it does not deteriorate . As a result, Property I is held, and the proof is completed. □
Property II. Considering an optimal solution to the reconfigurable HMRS scheduling problem complied with Property I, various sequences of batches processed with an identical configuration result in an equal .
Proof. Since no reconfiguration is required between processing successive batches of a machine with an identical configuration, altering their positions in the sequence does not impact . For instance, assume Figure 3(b) expresses an optimal schedule . Swapping with , leads to schedule (Figure 3(c)) with the same makespan. □
By employing these properties, instead of scheduling batches individually, we just need to schedule utilized configurations on each machine. For instance, if 10 batches are assigned to be processed by 3 configurations of a machine, instead of having 10! possibilities for the sequencing, the model just explores 3! possibilities. As a result, the performance of the models is significantly improved.
MILP model
Subject to:
Expression (4) indicates the objective function, i.e., makespan. Constraint (5) is related to assigning each order to a batch-machine-configuration combination respecting the configuration eligibility. Constraint (6) restricts the number of orders in a batch of a machine with a specific configuration to at most one item if its related batch processing limit equals 1. Constraint (7) concerns the formation of a batch on a machine and determines its configuration. Constraint (8) explains that an order can be assigned to a batch-machine-configuration combination if the related batch is formed. Machine processing height and area limits are respected in Constraints (9) and (10), respectively. Constraint (11) calculates the duration of each configuration on a machine based on the orders assigned to the relevant batches and required batch setup times. Constraint (12) relates that a batch on a machine with a specific configuration is formed if the corresponding configuration of the machine is utilized. Constraints (13) and (14) impose the required reconfiguration times from the initial configuration, and between utilized configurations on each machine, respectively. Moreover, they determine the completion times of configurations. The sequence of utilized configurations on each machine is specified in Constraints (15) and (16). Constraint (17) concerns the makespan. Constraint (18) defines the domains of the introduced variables.
CP model
In recent years, Constraint Programming has demonstrated itself as a competitive solution approach to tackle combinatorial optimization problems, specifically scheduling problems (e.g., [55, 56, 57]). It enjoys specific variables and functions with which a vast scope of problems can be effectively formulated.
In this paper, we adopt IBM ILOG CP Optimizer (CPO) to formulate the CP model. One of the main features of CP is the interval variable representing an activity. In CPO, the start, end, and duration of an interval can be recalled by startOf(), endOf(), and sizeOf() functions. Moreover, if an interval is defined as optional, it can be present or absent in the schedule, which can be recalled by presenceOf function. In order to be familiarized with the basic information regarding the variables and functions in the CPO, you can refer to Laborie, Rogerie [58]. In the following, first, the relevant CP variables of the problem are defined, then, the CP model is formulated.
Variables
An optional interval variable signifying the assignment of order to batch of machine being processed with configuration
An optional interval variable signifying batch of machine being processed by configuration
An optional interval variable signifying configuration of machine
A sequence variable representing the sequence of configurations on machine in which index is tracked by types option for imposing reconfiguration times (i.e., )
Subject to:
Equation (19) is the objective function of the CP model minimizing the makespan. Order assignment is observed by Constraint (20) considering the machine-configuration eligibility. Constraint (21) respects the batching limit restriction. Configuration of a batch of a machine is specified by Constraint (22). Constraint (23) indicates that the assignment of an order to a batch-machine combination depends on the presence of the relevant batch interval. Constraints (24) and (25) observe the machine processing height and area limits, respectively. Constraint (26) determines the size of each batch interval () based on its assigned orders and the required setup time. Applying function, Constraint (27) ensures that there is no overlap among batch intervals with a same configuration. Constraint (28) expresses that a present configuration of a machine starts and ends with the first and last batches of the machine with this configuration, respectively. Constraint (29) imposes the reconfiguration time from the initial configuration of a machine if it is required. Constraint (30) applies function on sequence that guarantees that there is no overlap among its present intervals () on the machine. In addition, it respects reconfiguration times between the consecutive configurations of each machine specified in transition matrix .
Solution Methods
In the following subsections, the developed LBBD method and WMILP model are illustrated, respectively.
Logic-based Benders decomposition
LBBD is a known exact solution method for tackling complex combinatorial optimization problems [59]. Similar to Benders decomposition (BD), LBBD decomposes the original model into one master problem (MP) and one or multiple subproblems (SPs). However, LBBD rectifies BD's shortcomings in handling non-linear, integer, and mixed-integer SPs [60]. LBBD iterates between MP and SP(s). In minimization problems, at each iteration, the MP solution represents a lower bound (LB) for the original model, and it is used to generate SP(s). Besides, SP(s) contribute to the best upper bound (UB) and feasibility and optimality cuts that are added to the MP to remove previously reached solutions. LBBD terminates when MP and SP(s) reach a same objective, or a predefined termination condition is achieved (e.g., reaching a specific gap, or computational time or iteration limit) [60, 61]. Unlike BD, LBBD does not employ a conventional procedure to generate cuts. Instead, the cuts must be developed based on the structure of an investigating problem[62].
LBBD has been successfully applied in a variety of problems, including maximal covering location problem [63], railway scheduling [64], electric vehicle routing problem [65], integrated process configuration and production planning [66], shelf space allocation [67], integrated parallel machine scheduling and location problem [68], integrated lot-sizing and scheduling problem [57, 69], operating room scheduling [70], to name a few. In the following, the decomposition scheme of the reconfigurable HMRS scheduling problem, the relevant MP, SPs, optimality cut, and LBBD improvement are elaborated.
Problem decomposition
The overall procedure of the developed LBBD is presented in Figure 4. As can be seen, the MP is responsible for determining the assignment of each order to an eligible machine-configuration combination. On the other hand, each SPs is involved in batching the assigned orders and scheduling the batches on their relevant machines. As a result, there are one MP and independent SPs. It should be noted that the SPs are always feasible since there is no limit on the number of assigned orders to a machine or the completion time of a machine. If the maximum makespan of all SPs is equal to the MP's objective, then the solution is optimal, and the algorithm is terminated. Otherwise, it is sub-optimal. In this case, if the termination condition (e.g., computational time limit) is not met, for each SP with the makespan equal to the maximum makespan, an optimality cut is extended and added to the MP, and the algorithm proceeds. Each part of the LBBD procedure is detailed in the next subsections.

Figure 4. The overall procedure of the developed LBBD.
Master problem
The MP assigns orders to machine-configuration combinations, leaving orders batching and configurations scheduling on each machine to the SPs. Accordingly, the MP is a relaxation of the original model in which is transformed to . Moreover, (related to the sequencing of configurations), , , and are removed. The additional parameter and variables of the MP are as follows.
The minimum reconfiguration time to configuration of machine from its other configurations, including initial configuration.
1 if order is assigned to machine being processed with configuration ; 0, otherwise.
Completion time of machine .
Subject to:
Benders optimality cuts
x_{omc}, u_{mcc'}, w_{mc} \in {0,1}; \ Obj, ct_m \in \mathbb{R}^{+}, \quad \forall o \in \mathcal{O}, \forall m \in \mathcal{M}, \forall c,c' \in \mathcal{C}_m
Subproblems
Following solving the MP in iteration , an optimal solution with is achieved, determining the assignment of each order to a machine-configuration combination. In this regard, there are independent subproblems each representing a single machine scheduling problem determining the optimal batching of assigned orders (i.e., for machine , only orders where ) and scheduling of utilized configuration (i.e., ) to minimize the makespan. The SP model for machine and the relevant variables are as follows.
| 1 if order is assigned to batch of machine in iteration ; 0, otherwise
| The makespan of machine in iteration
Subject to:
Expression (40) represents the makespan of th subproblem (i.e., related to machine ) in iteration . Constraints (41)-(44) seek the batching of the assigned orders considering batch processing limit and accordingly determine the configuration of each formed batch. The machine processing area is respected in Constraints (43). Constraint (44) calculates the duration of each utilized configuration on the machine based on the assigned orders to the relevant batches and required batch setup times. Constraints (47)-(49) are related to the scheduling of the configurations incorporating reconfiguration times. Constraint (48) concerns the makespan. Constraint (49) defines the domains of the variables.
LBBD cut
In each iteration of the LBBD algorithm, if the maximum makespan obtained by solving each SP equals the objective of the MP, the optimal solution to the original model is found, and the algorithm terminates. Otherwise, if the termination condition is not met, an optimality cut is added to the MP based on the SPs with the makespan equal to the maximum makespan of all SPs. It should be noted that no feasibility cut is required since any assignment of orders to machine-configuration in the MP leads to feasible solutions to the SPs.
Accordingly, the cut is defined as Constraint (50). Where is the makespan found by solving the SP related to machine in iteration .
Theorem 1. Cut (50) is a valid optimality cut.
Proof. In the sub-sequent iterations, the two following cases can happen:
Case 1. the same assignments are made to machine , then the makespan will be bounded to .
Case 2. At least one of that takes 0, then the right side of the cut will take a negative value, and it will be non-binding.
As a result, this cut will not eliminate any new feasible solution in the subsequent iterations, and in the case of a same assignment, it will limit the makespan to .
LBBD improvement
Based on several preliminary experiments on large-sized problems, it was found that the developed LBBD algorithm can be time-consuming, mostly due to the complexity of the MP and its large solution space. In this regard, an optimality gap of can be set in the MP for its early termination. In this case, the optimality gap (between the best upper bound and lower bound) of the original model will be equal to or less than [72]. Moreover, if the ratio of the number of orders to machines is large (e.g., greater than 40), setting a time limit can lead to a faster termination of SPs and more iterations in a limited computational time for the LBBD. However, it may hurt to reach an optimal solution by generating less accurate optimality cuts that remove some optimal solutions. Nevertheless, these improvement strategies are very effective in finding near-optimal solutions for large-sized instances in a limited computational time.
Presenting a suitable starting point through the warm start technique to MILP models can significantly enhance their performance by helping the solver to shrink the problem, and pruning some parts of the search tree. This starting point can be a complete or partial solution. As a result, a better solution may be obtained within a shorter computational time. This initial solution can be generated by another MILP model, a heuristic, a metaheuristic, or a hybrid method. In this paper, in each iteration, the solution obtained by the MP in the last iteration is used (assignment of orders to machine-configuration and batching of orders) as a starting point for the MP.
Warm-started MILP
This paper applies a two-step procedure to generate a partial initial solution to warm start the MILP. In the first step, the MP model presented in § 5.2 with a modification is solved to specify the assignment of orders to machine-configurations (), and utilized configurations (). This modification is about a better approximation of reconfiguration times in each machine. In the MP, the minimum reconfiguration time to a utilized configuration is calculated considering all configurations of the corresponding machine. While in Constraints (53)-(56), it is calculated according to utilized configurations on the machine. This leads to a tighter lower bound. Constraints (50)-(53) are not utilized in the MP due to the presence of big-M constraints that deteriorate the speed of solving procedure, and the MP needs to be solved several times. On the contrary, for warm starting the MILP model, it is solved just once. As a result, a tighter lower is useful to achieve a better initial solution.
1 if is the minimum reconfiguration time to configuration among the utilized configuration on machine ; 0, otherwise.
Constraints (53)–(56) calculate the minimum possible reconfiguration time to a utilized configuration () based on the relevant utilized and initial configurations of the corresponding machine. In these constraints, is a binary variable equals to 1 if is the minimum reconfiguration time to configuration among the utilized configuration on machine ; 0, otherwise.
In the second step, for each machine the following MILP model is solved to determine the batching of the assigned orders on each machine () with the objective of minimizing the number of batches (Equation (57)). Eventually, the assignment of orders to batch-machine-configuration combinations can be achieved (). This partial solution is utilized as starting point to the MILP model.
Subject to:
The descriptions of Constraints (58)-(62) are as the same as Constraints (41)-(45).
Constraint (63) specifies the variables of the model.
Computational experiments
This section concentrates on providing comprehensive computational experiments. In this regard, the way of generating random instances is illustrated first. Afterward, the performance of the LBBD method in solving the random instances is contrasted with that of MILP, CP, and WMILP models. Finally, the sensitivity of results to the variation in the key parameters' values is assessed, which can provide valuable insights.
To run the developed solution methods in each experiment, the IBM CPLEX Optimization Studio 20.1.0 solver is employed, and its related DOcplex.MP and DOcplex.CP libraries are imported into the Python 3.8 programming language. All the related scripts are executed on a computer with an Intel (R) Core (TM) i5–7300HQ processor and 12 GB of RAM.
Instance generation
In order to evaluate and compare the performance of the developed solution methods, multiple instances are generated randomly, inspired by data presented in [42, 73]. These instances include different numbers of orders {50, 100, 200, 300, 400, 600, 800}, configurations per machine {5, 10, 15, 20}, and machines {5, 10, 20, 30 40}. Note that the efficiency of an algorithm may be measured as a function of the size of the instance, i.e., the number of orders. The experiments in our study are specifically designed to include large-scale industrial instances with up to 800 orders, 20 configurations, and 40 machines and satisfy the design features including being: comprehensive and discriminant when multiple algorithms are compared. The instances are signified with -- to represent the number of orders, the number of specific configurations belonging to each machine, and the number of machines. For example, 50-5-5 represents an instance with 50 orders, 5 configurations per machine, and 5 machines. As explained in § 1, by adding or removing modules to a machine (e.g., changing the head of a robotic arm) different configurations with different production capabilities can be attained. As a result, it is possible to process an order with multiple eligible machine-configuration combinations () as it is detailed in Table 2. The manner of the random instance generation is described in Table 2.
| Parameters | Values |
| Discrete uniform distribution (75,200) | |
| Ceil (normal distribution (500,150)) | |
| Discrete uniform distribution (20,100) | |
| machine – configuration speed coefficient, Uniform distribution (0.8,1.2) | |
| Discrete uniform distribution (6,8) | |
| On each machine – configuration, probability ( = 1) = 0.1 | |
| For each order, first selecting a random number of machine, then on each machine, randomly, between 1 and 75% of its configurations are eligible ( = 1) | |
| Discrete uniform distribution (15,30) |
Table 2. The manner of the random instance generation
Performance evaluation of the developed solution methods
20 medium- and large-sized instances are solved by the developed MILP, CP, and WMILP models, as well as the LBBD method, under 10-minute and 60-minute computational time limits. It should be noted that a gap of 1% in solving the master problem and a time limit of 1 minute in solving SPs were incorporated into the LBBD method. The results are presented in Table 3 and Table 4, including the best lower bound (Best_LB) and best objective (Best_Obj) found by the methods, Gap with the Best_LB, and Related Percentage Deviation (RPD) with the Best_Obj. Calculating the Gap and RPD is presented in Equations (62) and (65), respectively. Accordingly, the superiority of the LBBD over other methods is evident in both 10-minute and 60-minute time limits, excepting 100-5-5 in the 10-minute limit and 50-5-10 and 100-5-5 in the 60-minute limit.
| No. | -- | Best_LB | Best_Obj | MILP Gap | MILP RPD | CP Gap | CP RPD | WMILP Gap | WMILP RPD | LBBD Gap | LBBD RPD |
| 1 | 50-5-5 | 598.61 | 603.59 | 2.27% | 1.48% | 14.38% | 15.83% | 1.26% | 0.44% | 0.83% | 0.00% |
| 2 | 50-10-5 | 584.04 | 600.34 | 9.05% | 6.96% | 11.59% | 10.04% | 5.92% | 3.41% | 2.72% | 0.00% |
| 3 | 50-5-10 | 285.17 | 302.12 | 9.86% | 4.71% | 13.78% | 9.47% | 7.19% | 1.70% | 5.61% | 0.00% |
| 4 | 50-10-10 | 312.85 | 326.54 | 10.68% | 7.26% | 20.27% | 20.17% | 7.49% | 3.56% | 4.19% | 0.00% |
| 5 | 100-5-5 | 1079.36 | 1093.57 | 3.75% | 2.55% | 9.85% | 9.48% | 1.30% | 0.00% | 1.46% | 0.16% |
| 6 | 100-10-5 | 1128.77 | 1142.74 | 13.28% | 13.90% | 20.44% | 24.16% | 3.18% | 2.02% | 1.22% | 0.00% |
| 7 | 100-5-10 | 591.04 | 609.55 | 7.65% | 4.99% | 18.22% | 18.57% | 8.64% | 6.13% | 3.04% | 0.00% |
| 8 | 100-10-10 | 601.27 | 616.75 | 6.99% | 4.81% | 26.59% | 32.80% | 9.43% | 7.64% | 2.51% | 0.00% |
| 9 | 200-5-5 | 2330.59 | 2357.83 | 11.03% | 11.10% | 12.83% | 13.39% | 1.23% | 0.08% | 1.16% | 0.00% |
| 10 | 200-10-5 | 2155.50 | 2177.08 | 11.55% | 11.94% | 26.49% | 34.69% | 4.03% | 3.17% | 0.99% | 0.00% |
| 11 | 200-5-10 | 1172.70 | 1197.93 | 14.10% | 13.96% | 20.51% | 23.15% | 5.84% | 3.97% | 2.11% | 0.00% |
| 12 | 200-10-10 | 1154.98 | 1173.57 | 22.24% | 26.56% | 32.91% | 46.70% | 12.51% | 12.49% | 1.58% | 0.00% |
| 13 | 300-5-10 | 1745.34 | 1772.20 | 12.52% | 12.57% | 18.43% | 20.73% | 5.14% | 3.82% | 1.52% | 0.00% |
| 14 | 300-10-10 | 1643.81 | 1662.91 | 14.59% | 15.74% | 35.12% | 52.36% | 17.31% | 19.54% | 1.15% | 0.00% |
| 15 | 300-5-20 | 866.80 | 883.50 | 19.64% | 22.09% | 29.03% | 38.23% | 15.36% | 15.91% | 1.89% | 0.00% |
| 16 | 300-10-20 | 868.70 | 897.72 | 34.33% | 47.36% | 45.23% | 76.69% | 17.39% | 17.14% | 3.23% | 0.00% |
| 17 | 400-5-10 | 2266.69 | 2297.63 | 34.77% | 51.25% | 28.85% | 38.66% | 1.64% | 0.30% | 1.35% | 0.00% |
| 18 | 400-10-10 | 2209.48 | 2241.26 | 25.11% | 31.63% | 33.86% | 49.05% | 11.68% | 11.62% | 1.42% | 0.00% |
| 19 | 400-5-20 | 1166.54 | 1188.48 | 21.42% | 24.91% | 34.21% | 49.19% | 15.64% | 16.36% | 1.85% | 0.00% |
| 20 | 400-10-20 | 1107.72 | 1136.86 | 25.79% | 31.30% | 49.22% | 91.88% | 17.68% | 18.36% | 2.56% | 0.00% |
| Average | 15.53% | 17.35% | 25.09% | 33.76% | 8.49% | 7.38% | 2.12% | 0.01% |
Table 3. Comparing the performance of the developed MILP, CP, WMILP, and LBBD in the 10-minute time limit.
| No. | Best_LB | Best_Obj | MILP Gap | MILP RPD | CP Gap | CP RPD | WMILP Gap | WMILP RPD | LBBD Gap | LBBD RPD | |
| 1 | 50-5-5 | 598.61 | 603.59 | 2.20% | 1.40% | 12.18% | 12.93% | 1.26% | 0.44% | 0.83% | 0.00% |
| 2 | 50-10-5 | 584.04 | 598.14 | 5.93% | 3.80% | 10.92% | 9.61% | 5.77% | 3.62% | 2.36% | 0.00% |
| 3 | 50-5-10 | 285.17 | 298.08 | 9.40% | 5.59% | 10.30% | 6.65% | 4.33% | 0.00% | 5.45% | 1.19% |
| 4 | 50-10-10 | 312.85 | 322.55 | 12.45% | 10.79% | 19.43% | 20.39% | 6.48% | 3.72% | 3.01% | 0.00% |
| 5 | 100-5-5 | 1079.36 | 1090.92 | 2.45% | 1.43% | 6.84% | 6.20% | 1.06% | 0.00% | 1.28% | 0.23% |
| 6 | 100-10-5 | 1128.77 | 1142.74 | 7.30% | 6.55% | 14.06% | 14.94% | 2.86% | 1.69% | 1.22% | 0.00% |
| 7 | 100-5-10 | 591.05 | 609.55 | 7.36% | 4.67% | 11.39% | 9.43% | 5.16% | 2.24% | 3.04% | 0.00% |
| 8 | 100-10-10 | 601.28 | 615.37 | 7.88% | 6.07% | 21.62% | 24.67% | 7.04% | 5.11% | 2.29% | 0.00% |
| 9 | 200-5-5 | 2333.21 | 2357.26 | 3.44% | 2.51% | 8.62% | 8.31% | 1.12% | 0.10% | 1.02% | 0.00% |
| 10 | 200-10-5 | 2155.50 | 2174.75 | 11.52% | 12.02% | 14.92% | 16.49% | 2.26% | 1.41% | 0.89% | 0.00% |
| 11 | 200-5-10 | 1172.70 | 1193.26 | 4.22% | 2.60% | 15.30% | 16.03% | 3.98% | 2.35% | 1.72% | 0.00% |
| 12 | 200-10-10 | 1154.99 | 1171.89 | 24.82% | 31.10% | 25.35% | 32.02% | 9.73% | 9.18% | 1.44% | 0.00% |
| 13 | 300-5-10 | 1745.34 | 1769.27 | 11.76% | 11.80% | 16.89% | 18.70% | 4.53% | 3.32% | 1.35% | 0.00% |
| 14 | 300-10-10 | 1643.81 | 1661.94 | 16.25% | 18.10% | 28.02% | 37.41% | 8.39% | 7.97% | 1.09% | 0.00% |
| 15 | 300-5-20 | 866.80 | 883.40 | 22.13% | 26.01% | 25.13% | 31.05% | 9.43% | 8.34% | 1.88% | 0.00% |
| 16 | 300-10-20 | 869.56 | 894.18 | 21.17% | 23.36% | 33.13% | 45.43% | 13.07% | 11.86% | 2.75% | 0.00% |
| 17 | 400-5-10 | 2266.69 | 2286.49 | 9.71% | 9.79% | 18.05% | 20.97% | 1.40% | 0.54% | 0.87% | 0.00% |
| 18 | 400-10-10 | 2209.48 | 2235.31 | 24.49% | 30.91% | 28.20% | 37.66% | 11.27% | 11.41% | 1.16% | 0.00% |
| 19 | 400-5-20 | 1166.54 | 1188.48 | 20.81% | 23.94% | 23.23% | 27.86% | 11.11% | 10.42% | 1.85% | 0.00% |
| 20 | 400-10-20 | 1107.85 | 1131.05 | 16.27% | 16.98% | 35.56% | 52.01% | 2.40% | 0.35% | 2.05% | 0.00% |
| Average | 12.12% | 12.47% | 19.00% | 22.44% | 5.63% | 4.20% | 1.88% | 0.07% |
Table 4. Comparing the performance of the developed MILP, CP, WMILP, and LBBD in the 60-minute time limit.
To better contrast the performance of the developed methods, the average Gap and RPD obtained by each method in the 10-minute and 60-minute time limits are depicted in Figure 5 and Figure 6, respectively. The LBBD, as the best method, managed to obtain solutions with a remarkable average Gap of 2.12 (in the 10-minute limit) and 1.88 (in the 60-minute limit). It can be inferred that the LBBD can reach near-optimal solutions in the early stages of its executions, and no major improvement occurs later. This is mostly due to the quality of SPs' makespan approximation in the MP model. In addition, the WMILP model also exhibits a decent performance by obtaining an 8.49% Gap (in 10 mins) and a 5.63% Gap (in 60 mins). Moreover, the MILP and CP models do not demonstrate a promising performance regarding the Gap. Furthermore, with respect to the average RPD shown in Figure 6, the supremacy of the LBBD method is also distinct from the other methods. Furthermore, it is observed that the average RPD of the MILP, CP, and WMILP are improved during their execution.

Figure 5. Comparing the developed solution methods regarding the average Gap

Figure 6. Comparing the developed solution methods regarding the average RPD
Based on the results, it can be concluded that the developed LBBD is an efficient solution method for the problem under consideration since it can provide near-optimal solutions for medium- and large-sized problems within a reasonably short computational time.
Table 5 is also designed to test the computational limitations of the LBBD on large-sized instances. In Table 4, we observed that the number of orders impacts the solution quality. Therefore, we report the results for two extreme values of and as well as two values of 30 and 40 for . Specifically, in Table 5, we evaluate the performance of LBBD for four different values of to analyze the complexity of reconfiguration decisions.
| No. | Gap | Iteration | Gap | Iteration | Gap | Iteration | Gap | Iteration | Average Gap | Average Iteration | |
| 1 | 600-30 | 2.07% | 45 | 2.01% | 48 | 2.09% | 31 | 2.69% | 28 | 2.21% | 38 |
| 2 | 800-40 | 1.67% | 19 | 2.42% | 19 | 3.15% | 6 | 4.33% | 1 | 2.89% | 11.25 |
| Average | 1.87% | 32 | 2.21% | 33.5 | 2.62% | 18.50 | 3.51% | 14.50 |
Table 5. Performance of the LBBD for large-sized instances with varying numbers of configurations, a termination condition of 2% optimality gap in the MP, and a 60-minute time limit for the LBBD.
For large-sized industrial instances, the initial settings of the MP and SPs of LBBD do not always guarantee the best performance, as the MP may consume a large portion of the time limit to generate a solution. In such cases, the optimality gap of 1% used for solving the MP for its early termination in Table 4 is increased to 2% in Table 5 to better align with the LBBD method. This adjustment allows for faster termination of the MP and enables more iterations of the LBBD within the 60-minute time limit, although it may result in a lower-quality MP solution.
It is interesting to observe that the Gaps in Table 5 are relatively consistent with those in Table 4 for =5, indicating that the LBBD remains effective in large-sized instances where MILP, CP, and WMILP become computationally impractical. When alternates between 10 and 20, the LBBD continues to perform effectively in finding near-optimal solutions for large-sized instances. Nevertheless, we can observe that gaps slightly diverge for larger values of in Table 5. For example, let us analyze 600-20-30 and 800-20-40, respectively. For 600-20-30, setting a 2% optimality gap in the MP helps solve the problem effectively, achieving a solution Gap of 2.69%. This setting also leads to 28 iterations, which are sufficient. In contrast, the largest instance, with a size of 800-20-40, demonstrates that the LBBD may not always achieve a reasonable solution when the MP optimality gap is fixed at 2%. This is evident from the solution Gap of 4.33% for this instance in Table 5. More importantly, the number of iterations is only one, which is not sufficient. An approach to address this issue is to further increase the 2% optimality gap of the MP. However, a larger optimality gap in the MP risks transforming the LBBD from an exact method into a heuristic approach.
The Gantt chart for instance 200-5-10, obtained by the LBBD method within the 60-minute time limit, is depicted in Figure 7. In this figure, the batches of a machine with the same configuration are presented by the same color. In addition, reconfiguration times and setup times are shown with black and grey colors, respectively.

Figure 7. Gantt chart for instance 200-5-10 obtained by the LBBD within 60-minute computational time
Sensitivity analysis
In this subsection, the impact of parameters' variation on the performance of the LBBD method and the scheduling outcome of the studied production system are explored. In this regard, the obtained solution gap of the LBBD method is regarded as its performance indicator. Furthermore, the achieved makespan is considered as the schedule performance indicator. To perform the analysis, the instance structure of 50-5-5 is considered. The analysis involves variations in the number of configurations per machine (3, 5, 7), number of machines (5, 7, 10), percentage of the eligible machine-configurations (30%, 50%, 70%), reconfiguration time (-50%, 0, 50%), setup time (-50%, 0, 50%), processing area (-50%, 0, +50%), and processing time variance (-50%, 0, +50%). For each experiment, 3 instances with different relevant parameters' values are generated and solved by the LBBD method, and the average results are reported. The analysis is illustrated in the following subsections.
Impact of the parameters' variations on the Gap
Figure 8 demonstrates the performance of the LBBD method in terms of the variation of different parameters. As it can be perceived, increasing the number of configurations, number of machines, percentage of the eligible machine-configurations, reconfiguration time, setup time, and processing area, and decreasing the processing time variance result in higher Gaps. Accordingly, variations in the number of machines (Figure 8b), reconfiguration time (Figure 8d), and setup time (Figure 8e) have the largest impacts on the obtained solution Gaps. For instance, increasing the number of machines from 5 to 10 leads to about a 6% surge in the Gap (Figure 8b). Moreover, the changes in the value of the processing area (Figure 8f) and processing time variance (Figure 8(g)) have the least effect on the LBBD performance.

(a)

(b)

(c)

(d)

(e)

(f)
Figure 8.
Overall, the LBBD method exhibits a rather robust performance against parameters' variations.

Figure 8g. Impact of the parameters' variations on the Gap
Impact of the parameter variation on the makespan
Figure 9 concerns the sensitivity analysis based on the efficiency of schedules. In this regard, Figure 9a shows that the number of configurations has no major impact on the makespan, whereas changing the number of machines from 5 to 10 sharply reduces the makespan by about 47% (Figure 9b). In contrast to Figure 9a, Figure 9c also shows that the increase in the percentage of eligible machine-configuration combinations from 30% to 70% leads to about a 3% reduction in the makespan. Thus, employing more versatile machines' modules enhances the flexibility and efficiency of the HMRSs, which should be pondered considering technical and budget limits.

(a) Fig. 9(a)

(b) Fig. 9(b)

(c) Fig. 9(c)

(d) Fig. 9(d)

(e) Fig. 9(e)

(f) Fig. 9(f)
Figure 9. Impact of the parameters' variations on the makespan
According to Figure 9d and Figure 9e, alternations in the reconfiguration time and setup time have a meaningful effect on the efficiency of the HMRSs. For instance, a 50% reduction in reconfiguration time leads to about a 5.6% improvement in the makespan.
Figure 9f reveals that the increase in the machine's processing area can strengthen the HMRSs' efficiency due to the reduction in the total setup times of machines. For instance, about 2% improvement can be achieved by a 50% increase in the processing area of machines.
Managerial insights and discussions
To this end, we shed light on the effect of parameters’ variation on the performance of the LBBD method, and the quality of the schedule by analyzing the solution Gap and makespan, respectively. Let us now consider Figure 8 and Figure 9 simultaneously in order to obtain additional managerial insights into the results presented in this section.
Proceeding in this manner reveals two types of parameters: low and high-priority parameters. The former type of parameters requires less attention, as they have no major influence on the Gap and makespan concurrently, i.e., the number of configurations, eligible machine-configuration combinations, processing area variation, and processing time variance. The conclusion from this comparison is that technical and budget allocation constraints should not be prioritized based on these types of parameters.
Conversely, the latter types of parameters should receive special attention from decision-makers as they can be related to strategic and tactical planning. For example, the relationship between the Gap and makespan performance indicators in Figure 8b and Figure 9b is strongly conflicting when the number of machines is changed. Hence, we can conclude that the policymaker should decide on the right number of machines such that an appropriate balance is achieved between the Gap and makespan. Deciding on the right number of machines is crucial in strategic and tactical decisions to balance underutilization and responsiveness.
Figure 8d and Figure 9d reveal that no conflict exists between the Gap and makespan indicators when the analysis is limited to the reconfiguration time variation. Therefore, providing appropriate modules for machines that can be easily and effortlessly reconfigured is among managerial decisions that should be made only based on technical and budget constraints. Likewise, Figure 8e and Figure 9e establish a conflict-free environment in the HMRS, posing no difficulty regarding the setup time variation. Setup is among the managerial decisions that should be made meticulously based on technical and budget constraints. Furthermore, providing workers with proper training programs can be promising in reducing both reconfiguration time and setup time, particularly in complex environments like HMRSs.
The results presented in this section align with those in § 6.2, reinforcing the reliability of the findings. More precisely, the insights gained from § 6.2 and § 7 are also applicable to various HMRSs for handling dynamic and real-time changes in scheduling parameters. The benefit of fast convergence of solutions (i.e., a gap of 2.12% with the Best_LB within the 10-minute limit, as shown in Table 3 and Figure 5) for dynamic scheduling of HMRSs is significant, as it directly impacts the HMRSs’ ability to adapt to changing conditions and make timely decisions. It can be concluded that rapid convergence minimizes the time required to generate and implement new schedules in real-time and respond quickly to dynamic conditions, such as new orders or changes in demand.
Conclusions and future research
This study investigated a batch production scheduling problem in a hybrid manufacturing-remanufacturing system comprising parallel reconfigurable machines. Accordingly, novel MILP and CP models were devised for the problem considering the makespan as the performance measure. The problem is highly complex due to the simultaneous decisions regarding assigning orders to machine-configuration combinations, batching orders in machines, and scheduling orders. In this regard, an efficient logic-based benders decomposition method was developed. In addition, the presented MILP model was enhanced by the warm start technique.
The computational experiments revealed the superiority of the LBBD method over the other developed solution methods by achieving the average Gap and RPD of 1.88% and 0.07%, respectively. Moreover, the results expressed that the variations in the number of machines, reconfiguration time, and setup time had the largest impacts on the LBBD method's performance. Furthermore, concerning the sensitivity analysis based on the makespan, it can be concluded that the number of machines, percentage of eligible machine-configuration combinations, reconfiguration time, setup time, and processing area were significantly impactful. Thus, proper decision-making at strategic and tactical levels regarding the number, specifications, and versatility of machines and their modules respecting the technical and budget limits, as well as suitable worker training are of great importance in the HMRSs.
Human well-being and energy consumption are among the most challenging issues confronting nowadays manufacturing industry. In this line, incorporating human-related objectives like ergonomics, workload balancing, and worker satisfaction can be explored to extend this study. In addition, considering different energy consumptions due to different configurations and the presence of time of use energy cost in the problem are promising directions for future studies.
Declaration of Competing Interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
Acknowledgment
This work was co-funded by the European Union under the project ROBOPROX (reg. no. CZ.02.01.01/00/22_008/0004590).
References
- [1][1]. Why the circular economy is the business opportunity of our time. 2022, https://www.weforum.org/agenda/2022/05/why-the-circular-economy-is-the-business-opportunity-of-our-time/. [accessed 8 September 2024]
- [2][2]. Suzanne, E., N. Absi, and V. Borodin, Towards circular economy in production planning: Challenges and opportunities. European Journal of Operational Research 2020; 287(1): 168-190. https://doi.org/10.1016/j.ejor.2020.04.043.
- [3][3]. Taleizadeh, A.A., M.S. Moshtagh, B. Vahedi-Nouri, and B. Sarkar, New products or remanufactured products: Which is consumer-friendly under a closed-loop multi-level supply chain? Journal of Retailing and Consumer Services 2023; 73: 103295. https://doi.org/10.1016/j.jretconser.2023.103295.
- [4][4]. Caterino, M., M. Fera, R. Macchiaroli, and D.T. Pham, Cloud remanufacturing: Remanufacturing enhanced through cloud technologies. Journal of Manufacturing Systems 2022; 64: 133-148. https://doi.org/10.1016/j.jmsy.2022.06.003.
- [5][5]. Kennedy, S. and M.K. Linnenluecke, Circular economy and resilience: A research agenda. Business Strategy and the Environment 2022; 31(6): 2754-2765. https://doi.org/10.1002/bse.3004.
- [6][6]. Institution, B.S., Design for Manufacture, Assembly, Disassembly and End-of-life Processing (MADE): Terms and Definitions. 2009: British Standards Institution.
- [7][7]. Zhang, W. Y. Zheng, and R. Ahmad, An energy-efficient multi-objective scheduling for flexible job-shop-type remanufacturing system. Journal of Manufacturing Systems 2023; 66: 211-232. https://doi.org/10.1016/j.jmsy.2022.12.008.
- [8][8]. Rizova, M.I., T. Wong, and W. Ijomah, A systematic review of decision-making in remanufacturing. Computers & Industrial Engineering 2020; 147: 106681. https://doi.org/10.1016/j.cie.2020.106681.
- [9][9]. Shi, J., S. Fan, Y. Wang, and J. Cheng, A GHG emissions analysis method for product remanufacturing: A case study on a diesel engine. Journal of Cleaner Production 2019; 206: 955-965. https://doi.org/10.1016/j.jclepro.2018.09.200.
- [10]Parker, D., K. Riley, S. Robinson, H. Symington, J. Tewson, K. Jansson, S. Ramkumar, and D. Peck, Remanufacturing market study. 2015.
- [11]Wang, J., X. Liu, W. Zhang, and J. Xu, A new remanufacturing system scheduling model with diversified reprocessing routes using a hybrid meta-heuristic algorithm. Concurrent Engineering 2022; 30(3): 283-299. https://doi.org/10.1177/1063293X221114666.
- [12]Fang, C.-C., M.-H. Lai, and Y.-S. Huang, Production planning of new and remanufacturing products in hybrid production systems. Computers & Industrial Engineering 2017; 108: 88-99. https://doi.org/10.1016/j.cie.2017.04.015.
- [13]Assid, M., A. Gharbi, and A. Hajji, Production control of failure-prone manufacturing-remanufacturing systems using mixed dedicated and shared facilities. International Journal of Production Economics 2020; 224: 107549. https://doi.org/10.1016/j.ijpe.2019.107549.
- [14]Reddy, K.N. and A. Kumar, Capacity investment and inventory planning for a hybrid manufacturing-remanufacturing system in the circular economy. International Journal of Production Research 2021; 59(8): 2450-2478. https://doi.org/10.1080/00207543.2020.1734681.
- [15]Garbie, I.H., DFSME: design for sustainable manufacturing enterprises (an economic viewpoint). International Journal of Production Research 2013; 51(2): 479-503. https://doi.org/10.1080/00207543.2011.652746.
- [16]Aljuneidi, T. and A.A. Bulgak, A mathematical model for designing reconfigurable cellular hybrid manufacturing-remanufacturing systems. The International Journal of Advanced Manufacturing Technology 2016; 87: 1585-1596. https://doi.org/10.1007/s00170-016-9141-z.
- [17]Aljuneidi, T. and A.A. Bulgak, Designing a Cellular Manufacturing System featuring remanufacturing, recycling, and disposal options: A mathematical modeling approach. CIRP Journal of Manufacturing Science and Technology 2017; 19: 25-35. https://doi.org/10.1016/j.cirpj.2017.04.005.
- [18]Koren, Y. and M. Shpitalni, Design of reconfigurable manufacturing systems. Journal of Manufacturing Systems 2010; 29(4): 130-141. https://doi.org/10.1016/j.jmsy.2011.01.001.
- [19]Bortolini, M., F.G. Galizia, and C. Mora, Reconfigurable manufacturing systems: Literature review and research trend. Journal of Manufacturing Systems 2018; 49: 93-106. https://doi.org/10.1016/j.jmsy.2018.09.005.
- [20]Kratena, T., P. Vavruska, J. Sveda, and M. Valasek, Postprocessor for Verification of Robot Movements with Additional Axis after Toolpath Optimization. Procedia CIRP 2021; 101: 154-157. https://doi.org/10.1016/j.procir.2021.02.018.
- [21]Ehm, F., Scheduling and process planning for the dismantling shop with flexible disassembly mode and recovery level. Computers & Industrial Engineering 2024; 189: 109927. https://doi.org/10.1016/j.cie.2024.109927.
- [22]Shi, J., W. Zhang, S. Zhang, and J. Chen, A new bifuzzy optimization method for remanufacturing scheduling using extended discrete particle swarm optimization algorithm. Computers & Industrial Engineering 2021; 156: 107219. https://doi.org/10.1016/j.cie.2021.107219.
- [23]Wang, W., G. Tian, M. Luo, H. Zhang, G. Yuan, and K. Niu, More mixed-integer linear programming models for solving three-stage remanufacturing system scheduling problem. Computers & Industrial Engineering 2024; 194: 110379. https://doi.org/10.1016/j.cie.2024.110379.
- [24]Guo, J., J. Zou, B. Du, and K. Wang, Integrated scheduling for remanufacturing system considering component commonality using improved multi-objective genetic algorithm. Computers & Industrial Engineering 2023; 182: 109419. https://doi.org/10.1016/j.cie.2023.109419.
- [25]Tang, O. and R. Teunter, Economic lot scheduling problem with returns. Production and Operations Management 2006; 15(4): 488-497. https://doi.org/10.1111/j.1937-5956.2006.tb00158.x.
- [26]Teunter, R.O. Tang, and K. Kaparis, Heuristics for the economic lot scheduling problem with returns. International Journal of Production Economics 2009; 118(1): 323-330. https://doi.org/10.1016/j.ijpe.2008.08.036.
- [27]Zanoni, S., A. Segerstedt, O. Tang, and L. Mazzoldi, Multi-product economic lot scheduling problem with manufacturing and remanufacturing using a basic period policy. Computers & Industrial Engineering 2012; 62(4): 1025-1033. https://doi.org/10.1016/j.cie.2011.12.030.
- [28]Aminpour, A., Z. Bahroun, and M. Hariga, Cyclic manufacturing and remanufacturing in a closed-loop supply chain. Sustainable Production and Consumption 2021; 25: 43-59. https://doi.org/10.1016/j.spc.2020.08.002.
- [29]Giglio, D., M. Paolucci, and A. Roshani, Integrated lot sizing and energy-efficient job shop scheduling problem in manufacturing/remanufacturing systems. Journal of Cleaner Production 2017; 148: 624-641. https://doi.org/10.1016/j.jclepro.2017.01.166.
- [30]Roshani, A., M. Paolucci, D. Giglio, M. Demartini, F. Tonelli, and M.A. Dulebenets, The capacitated lot-sizing and energy efficient single machine scheduling problem with sequence dependent setup times and costs in a closed-loop supply chain network. Annals of Operations Research 2023; 321(1-2): 469-505. https://doi.org/10.1007/s10479-022-04783-4.
- [31]Torkaman, S., S.F. Ghomi, and B. Karimi, Hybrid simulated annealing and genetic approach for solving a multi-stage production planning with sequence-dependent setups in a closed-loop supply chain. Applied Soft Computing 2018; 71: 1085-1104. https://doi.org/10.1016/j.asoc.2017.10.019.
- [32]Koren, Y., X. Gu, and W. Guo, Reconfigurable manufacturing systems: Principles, design, and future trends. Frontiers of Mechanical Engineering 2018; 13(2): 121-136. https://doi.org/10.1007/s11465-018-0483-0.
- [33]Yelles-Chaouche, A.R., E. Gurevsky, N. Brahimi, and A. Dolgui, Reconfigurable manufacturing systems from an optimisation perspective: a focused review of literature. International Journal of Production Research 2021; 59(21): 6400-6418. https://doi.org/10.1080/00207543.2020.1813913.
- [34]Ye, H. and M. Liang, Simultaneous modular product scheduling and manufacturing cell reconfiguration using a genetic algorithm. Journal of Manufacturing Science and Engineering 2006; 128(4): 984-995. https://doi.org/10.1115/1.2336261.
- [35]Dou, J., J. Li, D. Xia, and X. Zhao, A multi-objective particle swarm optimisation for integrated configuration design and scheduling in reconfigurable manufacturing system. International Journal of Production Research 2021; 59(13): 3975-3995. https://doi.org/10.1080/00207543.2020.1756507.
- [36]Essafi, M., X. Delorme, and A. Dolgui, A reactive GRASP and Path Relinking for balancing reconfigurable transfer lines. International Journal of Production Research 2012; 50(18): 5213-5238. https://doi.org/10.1080/00207543.2012.677864.
- [37]Naderi, B. and A. Azab, Production scheduling for reconfigurable assembly systems: Mathematical modeling and algorithms. Computers & Industrial Engineering 2021; 162: 107741. https://doi.org/10.1016/j.cie.2021.107741.
- [38]Amaya, J.E., C. Cotta, and A.J. Fernandez-Leiva, Solving the tool switching problem with memetic algorithms. AI EDAM 2012; 26(2): 221-235. https://doi.org/10.1017/S089006041100014X.
- [39]Vahedi-Nouri, B., R. Tavakkoli-Moghaddam, Z. Hanzálek, and A. Dolgui, Workforce planning and production scheduling in a reconfigurable manufacturing system facing the COVID-19 pandemic. Journal of Manufacturing Systems 2022; 63: 563-574. https://doi.org/10.1016/j.jmsy.2022.04.018.
- [40]Vahedi-Nouri, B., R. Tavakkoli-Moghaddam, Z. Hanzalek, and A. Dolgui. Integrated Workforce Allocation and Scheduling in a Reconfigurable Manufacturing System Considering Cloud Manufacturing. in Advances in Production Management Systems. Artificial Intelligence for Sustainable and Resilient Production Systems. APMS 2021. IFIP Advances in Information and Communication Technology, vol 631. 2021. Springer, Cham.
- [41]Yang, S., J. Wang, L. Xin, and Z. Xu, Real-time and concurrent optimization of scheduling and reconfiguration for dynamic reconfigurable flow shop using deep reinforcement learning. CIRP Journal of Manufacturing Science and Technology 2023; 40: 243-252. https://doi.org/10.1016/j.cirpj.2022.12.001.
- [42]Vahedi-Nouri, B., R. Tavakkoli-Moghaddam, Z. Hanžálek, and A. Dolgui. Production scheduling in a reconfigurable manufacturing system benefiting from human-robot collaboration. International Journal of Production Research 2024; 62(3): 767-783. https://doi.org/10.1080/00207543.2023.2173503.
- [43]Delorme, X., G. Fleury, P. Lacomme, and D. Lamy, Modelling and solving approaches for scheduling problems in reconfigurable manufacturing systems. International Journal of Production Research 2024; 62(7): 2683-2704. https://doi.org/10.1080/00207543.2023.2224446.
- [44]Mahmoodjanloo, M., R. Tavakkoli-Moghaddam, A. Baboli, and A. Bozorgi-Amiri, Flexible job shop scheduling problem with reconfigurable machine tools: An improved differential evolution algorithm. Applied Soft Computing 2020; 94. https://doi.org/10.1016/j.asoc.2020.106416.
- [45]Guo, H., J. Liu, Y. Wang, and C. Zhuang, An improved genetic programming hyper-heuristic for the dynamic flexible job shop scheduling problem with reconfigurable manufacturing cells. Journal of Manufacturing Systems 2024; 74: 252-263. https://doi.org/10.1016/j.jmsy.2024.03.009.
- [46]Gao, S., J. Daaboul, and J. Le Duigou, Process Planning, Scheduling, and Layout Optimization for Multi-Unit Mass-Customized Products in Sustainable Reconfigurable Manufacturing System. Sustainability 2021; 13(23): 13323. https://doi.org/10.3390/su132313323.
- [47]Bensmaine, A., M. Dahane, and L. Benyoucef, A new heuristic for integrated process planning and scheduling in reconfigurable manufacturing systems. International Journal of Production Research 2014; 52(12): 3583-3594. https://doi.org/10.1080/00207543.2013.878056.
- [48]Rohaninejad, M., Z. Hanzálek, R. Tavakkoli-Moghaddam, and B. Vahedi-Nouri, Integrated Lot-sizing and Job Shop Scheduling Benefiting From Reconfigurable Machine Tools. IFAC-PapersOnLine 2022; 55(10): 1284-1289. https://doi.org/10.1016/j.ifacol.2022.09.567.
- [49]Fan, J., C. Zhang, W. Shen, and L. Gao, A matheuristic for flexible job shop scheduling problem with lot-streaming and machine reconfigurations. International Journal of Production Research 2023; 61(19): 6565-6588. https://doi.org/10.1080/00207543.2022.2135629.
- [50]Fan, J., C. Zhang, Q. Liu, W. Shen, and L. Gao, An improved genetic algorithm for flexible job shop scheduling problem considering reconfigurable machine tools with limited auxiliary modules. Journal of Manufacturing Systems 2022; 62: 650-667. https://doi.org/10.1016/j.jmsy.2022.01.014.
- [51]Mahmoodjanloo, M., R. Tavakkoli-Moghaddam, A. Baboli, and A. Bozorgi-Amiri, Distributed job-shop rescheduling problem considering reconfigurability of machines: a self-adaptive hybrid equilibrium optimiser. International Journal of Production Research 2022; 60(16): 4973-4994. https://doi.org/10.1080/00207543.2021.1946193.
- [52]Yang, S. and Z. Xu, Intelligent scheduling and reconfiguration via deep reinforcement learning in smart manufacturing. International Journal of Production Research 2022; 60(16): 4936-4953. https://doi.org/10.1080/00207543.2021.1943037.
- [53]Uzunoglu, A., C. Gahm, S. Wahl, and A. Tuma, Learning-augmented heuristics for scheduling parallel serial-batch processing machines. Computers & Operations Research 2023; 151: 106122. https://doi.org/10.1016/j.cor.2022.106122.
- [54]Rahmani, R., T.G. Crainic, M. Gendreau, and W. Rei, The Benders decomposition algorithm: A literature review. European Journal of Operational Research 2017; 259(3): 801-817.
- [55]Heinz, V., A. Novák, M. Vlk, and Z. Hanzálek, Constraint Programming and constructive heuristics for parallel machine scheduling with sequence-dependent setups and common servers. Computers & Industrial Engineering 2022; 172: 108586. https://doi.org/10.1016/j.cie.2022.108586.
- [56]Fatemi-Anaraki, S., R. Tavakkoli-Moghaddam, M. Foumiani, and B. Vahedi-Nouri, Scheduling of multi-robot job shop systems in dynamic environments: mixed-integer linear programming and constraint programming approaches. Omega 2023; 115: 102770. https://doi.org/10.1016/j.omega.2022.102770.
- [57]Rohaninejad, M. and Z. Hanzálek, Multi-level lot-sizing and job shop scheduling with lot-streaming: Reformulation and solution approaches. International Journal of Production Economics 2023: 108958. https://doi.org/10.1016/j.ijpe.2023.108958.
- [58]Labrobie, P.J., J. Rogerie, P. Shaw, and P. Vilím, IBM ILOG CP optimizer for scheduling: 20+ years of scheduling with constraints at IBM/ILOG. Constraints 2018; 23: 210-250. https://doi.org/10.1007/s10601-018-9281-x.
- [59]Hooker, J.N. and G. Ottosson, Logic-based Benders decomposition. Mathematical Programming 2003; 96(1): 33-60. https://doi.org/10.1007/s10107-003-0375-9.
- [60]Juvin, C., L. Houssain, and P. Lopez, Logic-based Benders decomposition for the preemptive flexible job-shop scheduling problem. Computers & Operations Research 2023; 152: 106156. https://doi.org/10.1016/j.cor.2023.106156.
- [61]Barzanji, R., B. Naderi, and M.A. Begen, Decomposition algorithms for the integrated process planning and scheduling problem. Omega 2020; 93: 102025. https://doi.org/10.1016/j.omega.2019.01.003.
- [62]Cao, Z., W. Wang, Y. Jiang, X. Xu, Y. Xu, and Z. Guo, Joint berth allocation and ship loader scheduling under the rotary loading mode in coal export terminals. Transportation Research Part B: Methodological 2022; 162: 229-260. https://doi.org/10.1016/j.trb.2022.06.004.
- [63]Fischer, V. and S. Wöhlk, A logic-based Benders decomposition solution approach for two covering problems that consider the underlying transportation. Computers & Operations Research 2023; 160: 106393. https://doi.org/10.1016/j.cor.2023.106393.
- [64]Leutwiler, F., G.B. Filella, and F. Corman, Accelerating logic-based Benders decomposition for railway rescheduling by exploiting similarities in delays. Computers & Operations Research 2023; 150: 106075. https://doi.org/10.1016/j.cor.2022.106075.
- [65]Lam, E., G. Desaulniers, and P.J. Stuckey, Branch-and-cut-and-price for the electric vehicle routing problem with time windows, piecewise-linear recharging and capacitated recharging stations. Computers & Operations Research 2022; 145: 105870. https://doi.org/10.1016/j.cor.2022.105870.
- [66]Martínez, K.P., Y. Adulyasak, and R. Jans, Logic-Based Benders Decomposition for Integrated Process Configuration and Production Planning Problems. INFORMS Journal on Computing 2022; 34(4): 2177-2191. https://doi.org/10.1287/ijoc.2021.1079.
- [67]Gencosman, B.C. and M.A. Begen, Exact optimization and decomposition approaches for shelf space allocation. European Journal of Operational Research 2022; 299(2): 432-447. https://doi.org/10.1016/j.ejor.2021.08.047.
- [68]Li, Y., J.-F. Côté, L. Callegari-Coelho, and P. Wu, Novel formulations and logic-based benders decomposition for the integrated parallel machine scheduling and location problem. INFORMS Journal on Computing 2022; 34(2): 1048-1069. https://doi.org/10.1287/ijoc.2021.1113.
- [69]Rohaninejad, M., B. Vahedi-Nouri, Z. Hanzálek, and R. Tavakkoli-Moghaddam, An integrated lot-sizing and scheduling problem in a reconfigurable manufacturing system under workforce constraints. International Journal of Production Research 2024; 62(11): 3994-4013. https://doi.org/10.1080/00207543.2022.2533111.
- [70]Naderi, B., V. Roshanaei, M.A. Begen, D.M. Aleman, and D.R. Urbach, Increased surgical capacity without additional resources: Generalized operating room planning and scheduling. Production and Operations Management 2021; 30(8): 2608-2635. https://doi.org/10.1111/poms.13397.
- [72]Tran, T.T., A. Araujo, and J.C. Beck, Decomposition methods for the parallel machine scheduling problem with setups. INFORMS Journal on Computing 2016; 28(1): 83-95. https://doi.org/10.1287/ijoc.2015.0666.
- [73]Rohaninejad, M., R. Tavakkoli-Moghaddam, B. Vahedi-Nouri, Z. Hanzálek, and S. Shirazian, A hybrid learning-based meta-heuristic algorithm for scheduling of an additive manufacturing system consisting of parallel SLM machines. International Journal of Production Research 2022; 60(20): 6205-6225. https://doi.org/10.1080/00207543.2021.1987550.