Integrating meta-heuristics and a Sarsa algorithm for disassembly scheduling problems with cycle time and hazard coefficients

Problem description

Disassembly is a comprehensive manufacturing process that detaches a variety of components at multiple workstations. During a disassembly process, n tasks need to be allocated among m workstations. To streamline the complexity of the problem, we assume that all workstations can disassemble any task and are functionally identical^[40]. A disassembly task involves a series of operations. Once a task is completed, the resulting components or sub-components can be further disassembled into their constituent parts until the core is entirely disassembled. In essence, the disassembly process is a progressive dismantling of the core into its individual components and subassemblies through a sequence of tasks. Upon satisfying the constraints, we allocate the disassembly tasks to specific workstations on the disassembly line, adhering to the disassembly order that meets the requirements. Once a task is assigned to a workstation, it becomes fixed and cannot be transferred to another workstation. It must be completed at the workstation. The number of available workstations remains constant, while different disassembly sequences can result in variations in disassembly time and hazard coefficients. The DLSP includes three sub-problems: (1) assigning tasks to workstations; (2) task sequencing; and (3) adjusting the task sequence to minimize the CT and hazard coefficients.

In DLSP, there are priority and time interference relationships between disassembly tasks. An example is shown in Figure 1, and the detail data is reported in Table 1. The numbers inside the circle represent disassembly tasks, and the solid arrow represents the priority order between tasks. Task 1 is the predecessor of Tasks 2, 3, and 4, indicating that Task 1 must be disassembled before proceeding with Tasks 2, 3, and 4. Tasks with the same background lines have a time interference relationship between them. Table 1 provides a detailed description of the example. For example, if Task 4 is disassembled first, it will increase the disassembly time of Task 5 by two units, and the actual disassembly time of Task 5 is 3 + 2 = 5 units. Conversely, if Task 5 is disassembled first, it will also increase the actual disassembly time of Task 4. Figure 2 shows the Gantt chart of a solution for the example.

Figure 1. Task disassembly sequence diagram.

Figure 2. The Gantt chart for task 7.

Mathematical models

In this section, a mathematical model of DLSP is developed with minimizing CT and hazard coefficients. The following notations s are used to express the concerned problems, and the detail data is reported in Table 2.

With defined notations, the mathematical representation of the DLSP can be formulated, as shown in Table 3.

Objective function (1) is calculated by assigning different weights to objective functions (2) and (3), where λ + ω = 1. Objective function (2) is to maximize the actual completion time among the running workstations. Objective function (3) is the total hazard coefficients of all hazard tasks. Constraint (4) indicates that there is a precedence relationship between task i and task j in the disassembly process. Constraint (5) states that the actual disassembly time for a task is the sum of its standard time and the interference time. Constraint (6) means that the processing order of tasks needs to satisfy the disassembly priority relationship. Constraint (7) ensures that the task is executed only once. Constraint (8) calculates the average processing time of all tasks. Constraint (9) enforces that the start time of a subsequent task should be greater than or equal to the completion time of the previous one. Constraint (10) states that the completion time of a task is equal to the sum of its start and the actual disassembly time. Constraint (11) defines that each task can be assigned to only one workstation. Constraint (12) represents the actual completion time of workstations. Constraints (13) to (16) give the sign constraints on the decision variables.

Solution representation

In DLSP, the order of disassembly tasks is optimized to minimize the CT and hazard coefficients, while ensuring the priority constraint of tasks. For example, there is an initial disassembly order, s = (7, 3, 4, 6, 2, 5, 1), representing the disassembly tasks in Figure 1. As depicted in Figure 1, s does not meet the priority of tasks. Consequently, by considering prioritization of tasks appropriately, s can be adjusted to s’ as follows: s’ = (1, 3, 4, 6, 2, 5, 7).

According to the characteristics of fixed workstations for this problem, two workstation assignment schemes are designed.

(1) The first step is to allocate the tasks among workstations randomly. Subsequently, based on task order and priority relationships, the tasks are sequentially disassembled on each workstation. According to the sequence s’, seven tasks were assigned to three workstations with 2, 2, and 3 tasks, respectively. The workstation 1 is for tasks 1 and 3, while workstation 2 processes tasks 4 and 6. The remaining three tasks are disassembled on workstation 3, as depicted in Figure 3. The detailed data is reported in Table 4.

Figure 3. The Gantt chart for the random workstation assignment scheme. CT: Cycle time.

(2) The tasks in a feasible sequence are assigned to the workstation list one by one. In one round, each workstation has only one task. A new round starts if there are remaining tasks in the sequence. Finally, all tasks can be assigned to all workstations. For example, according to the sequence s’ = (1, 3, 4, 6, 2, 5, 7), the total number of tasks is 7, and workstation number is 3. In the first round, task 1 is assigned to workstation 1, task 3 is assigned to workstation 2, and task 4 is assigned to workstation 3. In the next round, task 6 is assigned to workstation 1; the remaining tasks are assigned in the same way until all tasks are assigned. The final Gantt chart is depicted in Figure 4. The detailed data reported is in Table 5.

Figure 4. The Gantt chart for the second workstation assignment scheme. CT: Cycle time.

To clearly demonstrate the performance improvement of meta-heuristics combined with Sarsa, an example of 8 tasks is solved. Sarsa’s reward feedback can be utilized to select the appropriate task assignment for the problem size and through better choosing local search to obtain higher quality solutions. From Figure 5 to Figure 7, it can be clearly seen that the results by the meta-heuristics with Sarsa strategies are better than the algorithm without Sarsa strategies.

Figure 5. The Gantt chart for task 8. CT: Cycle time.

Figure 6. The Gantt chart for task 8 applying only meta-heuristics. CT: Cycle time.

Figure 7. The Gantt chart for task 8 applying the combination of metaheuristics with Sarsa. CT: Cycle time.

Meta-heuristics

This section describes four meta-heuristics: PSO, ABC, GA, and VNS. They start from parameter and population initialization. Then, the initial solutions are evaluated. After that, new solutions are generated by algorithm-specific strategies to update population. These steps are repeated until the termination condition is satisfied. The unified framework of the four algorithms is presented in Figure 8.

Figure 8. The unified framework of the four algorithms.

Sarsa

As a reinforcement learning algorithm, Sarsa is introduced to improve the adaptability and performance of Q-learning^[58]. The main difference between Sarsa and Q-learning is the strategy to update Q-value. The schematic representation of the Sarsa framework is depicted in Figure 9.

Figure 9. The framework of Sarsa.

The updating formula of Q-value in Sarsa is expressed as Equation (17).

where Q (S_t, A_t) is the Q-value of taking an action A_t at state S_t, α represents the learning rate, and R is the reward after executing action A_t. According to the problem of DLSP, the reward value formula is designed as Equation (18). γ is the discount factor, which takes values in the range [0,1].

Different from Q-learning, Sarsa can select an action under state S_t+1 according to different distributions of possible future returns for the current state, rather than directly selecting the largest expected Q-value to execute actions under the next state S_t+1. When updating the Q-table, Sarsa is still selecting the next action on the Q-table, which has not been updated yet. However, Q-learning chooses the next action on the updated Q-table.

For DLSP problems, we design a strategy π based on a probability distribution and set four values P = (0.7, 0.8, 0.9, 1), respectively. The action with the highest expected value is selected in the probability of P, and random selection is executed under the probability of (1 - P), as depicted in Equation (19).

Sarsa based task assignment

Two workstation assignment schemes are presented in Section “Solution representation”. The Sarsa algorithm is used to select an appropriate workstation assignment scheme (action) during meta-heuristics’ iterations. The initial Q-table is shown in Table 6. Each solution corresponds to a state S, while each action A represents a workstation assignment scheme. If a solution is improved by executing a workstation allocation strategy, a reward is obtained and the corresponding Q-value is updated. The ratio of the workstation allocation scheme being selected for the next iteration is increased. Conversely, if a solution is not improved, there is no reward and its selection probability in the next iteration decreases. The π strategy is employed for action selection. Through continuous exploration and feedback in the learning process, the algorithm can discern better task allocation methods tailored to different requirements. Algorithm 1 describes the steps of this task assignment strategy.

Algorithm 1. Sarsa based task assignment

Sarsa based local search

This article introduces ten local search operators for enhancing the performance of the meta-heuristics, which includes the adjustments for CT time and hazard coefficients. The detailed procedures of ten local searches are delineated below:
(1) Swap: Swap the positions of two random tasks in the sequence [Figure 10A].
(2) Double swap: Repeat the swap operation twice [Figure 10B].
(3) Insertion: Randomly take out a task from a sequence and insert it into a new position in the sequence [Figure 10C].
(4) Bind insertion: Randomly select two consecutive tasks from a task sequence and insert them at the position with the lowest desired target value [Figure 10D].
(5) Block insertion: Randomly select multiple consecutive tasks from a task sequence and insert them at the position with the lowest desired target value [Figure 10E].
(6) Insert sequentially: Randomly select multiple tasks in a task sequence and insert them into the sequence one by one with the lowest desired target value [Figure 10F].
(7) Inverse: Randomly select several consecutive tasks from a task sequence in their reverse order [Figure 10G].
(8) Sort: Adjust the hazard task to the next position that satisfies the priority relationship [Figure 10H].
(9) Random sort: Randomly adjust the hazardous task to the sequence position with satisfying the priority relationship [Figure 10I].
(10) Sort sequentially: Adjust the hazardous tasks in sequence to a new position with satisfying the priority relationship and the lowest target value [Figure 10J].

Figure 10. The framework of Sarsa.

Sarsa is employed to select premium local search operators during iterations. The solutions are as states while ten local search operators are taken as actions. In the learning process, the π strategy is used to select actions for the next state. If the current action gets a better solution, there is a position reward, increasing its probability of being selected in the next iteration. In contrast, the probability of being selected in the next iteration is decreased.

If the sequence obtained by local search does not satisfy the priority relationship, we need to update it to a feasible solution. The steps of Sarsa based local search are described in Algorithm 2.

Algorithm 2. Sarsa based local search

Framework of the proposed algorithms

The improved strategies are embedded in four meta-heuristics. The unified framework of them is shown in Figure 11. All algorithms start from an initial population and iteratively update population with their respective strategies. During iterations, two Sarsa based strategies are employed to improve the exploration and exploitation of meta-heuristics. Finally, the best result is output if the termination condition is met.

Figure 11. The framework of the proposed algorithms.

Experimental setup

To verify the effectiveness of the proposed strategies, ten instances with different scales are solved^[59]. All the algorithms are compiled in C++; the running platform is a desktop computer with an Intel Core i7-10,700 CPU @ 2.90 GHz and 16 GB of RAM under Microsoft Windows 11.

To ensure a fair comparison, all algorithms are executed for the same termination time, four seconds, while their parameters are experimentally determined to achieve the optimal combination. The algorithm’s performance is assessed by comparing its average value, minimum value, and the coefficient of variation (CV) in 20 runs. The smaller the CV value, the better the stability and robustness of the algorithm is.

The formula for calculating CV is as follows:

where AVE is the average of the target values obtained in 20 runs, and SD is the corresponding standard deviation.

Parameter setting

The orthogonal experiment design method is used to test the influence of parameters on the performance of the four combined algorithms. Taking the SPSO_SD as an example, there are four parameters, which are limited iterations (L), population size (Ps), learning rate (α), and discount rate (γ). Each parameter is set to four values, L ∈ {10, 20, 30, 40}, Ps ∈ {10, 20, 30, 40}, α ∈ {0.2, 0.4, 0.6, 0.8}, and γ ∈ {0.05, 0.1, 0.15, 0.2}. The orthogonal matrix L₁₆ (4⁴) is shown in Table 7. By solving each group of parameters in the SPSO_SD and analyzing the target values obtained from experimental results, a corresponding main effect diagram is constructed, as depicted in Figure 12. It is evident that the SPSO_SD has the best results under the parameter combination, L = 20, Ps = 20, α = 0.8, and γ = 0.1, which is adopted for further test and comparisons.

Figure 12. The main effects plot for SPSO_SD.

In ABC, there are three parameters, employed bees (Ep), onlooker bees (Op), and scout bees (Sp), Op = 1 - Ep - Sp. By the trend of the parameter hierarchy of Figure 13, we choose the combination Ep = 0.5, Op = 0.2, and Sp = 0.3. In GA, there are two important parameters: crossover probability and mutation probability. After parameter tuning experiments, we choose Pc = 0.7 and Pm = 0.3, as depicted in Figure 14. In VNS, the maximum number of iterations and the number of domain operations have an important impact on the performance, and experimentally, the algorithm performs best when L = 20 and M = 30, as depicted in Figure 15.

Figure 13. Parameter level trend of ABC. ABC: Artificial bee colony.

Figure 14. Parameter level trend of GA. GA: Genetic algorithm.

Figure 15. Parameter level trend of VNS. VNS: Variable neighborhood search.

We design a strategy π based on probability distribution. To choose a better probability setting, the largest instance is solved under six probabilities (P = 0.5, 0.6, 0.7, 0.8, 0.9, 1) with 20 runs independently. The first 20 optimal values under six probabilities are selected to judge the number of distributions in each probability, as shown in Figure 16. The best four probability values are selected, (P = 0.7, 0.8, 0.9, 1).

Figure 16. The number proportion of the optimal values of six probabilities.

Verifying the effectiveness of improved strategies

To verify the effectiveness of the proposed strategies, four meta-heuristics are compared to their respective variants. For all cases, the average (Ave) and minimum (Min) values of results are reported in Tables 8-11. From Table 8, SPSO_SD has the best results, with the best results for all cases and the smallest mean values. As shown in Table 9, SABC_SD has the smallest mean values for all cases and gets the best results in seven examples. The SABC_RD gets the best results for one case, while ABC_SD gets the best results in four cases. As reported in Table 10, SGA_SD obtains the smallest mean values for all cases and achieves the best results for five cases. The SGA_RD achieves the best results for only 1 case, while the GA_SD gets the best results for five cases. In Table 11, SVNS_SD has the smallest mean values for all cases and achieves the best result for seven cases. The SVNS_RD achieves the best result for one case. The VNS_SD achieves the best result for two cases while the VNS does not obtain the best mean value and minimum value for any case. It can be concluded that the meta-heuristics combined with Sarsa based task assignment and local search strategies have better robustness and stability than the compared ones.

The CV is employed as a metric to assess the influence of enhancement strategies on algorithms’ stability and robustness. Tables 12-15 show the comparisons of CV among the four classical meta-heuristics and their variants, respectively. In Table 12, SPSO_SD receives the best Min values for eight out of ten cases. As shown in Table 13, the SABC_SD obtains the minimum values for eight cases, while the ABC_SD obtains the minimum values for two cases. As reported in Table 14, the SGA_SD obtains the minimum values for seven out of ten cases, while GA_SD gets the minimum values for two cases. In Table 15, SVNS_SD obtains the minimum values for eight cases, while the VNS_SD and SVNS_RD obtain the minimum value for one case. In each group, the algorithm with two Sarsa based strategies has smaller CV values for most instances. This means that the Sarsa based strategies can improve the stability and robustness of four meta-heuristics.

Further comparisons and discussions

To further verify the performance difference among four algorithms with Sarsa based strategies, the Friedman test and Nemenyi post-test are executed. The results are represented in Table 16, Figures 17 and 18. In Table 16, the obtained asymptotic significance (Asymp.Sig) is far less than 0.05, indicating noteworthy disparities among the four algorithms. It implies that there exist significant variations in their performance. Figure 17 shows the mean rank of algorithms by Nemenyi post-test. It is obvious that the SPSO_SD has the smallest rank value (1.70). Figure 18 visually presents the algorithm ranking distribution for all cases. It can be seen from Figure 18 that the SPSO_SD ranks first for six out of ten instances and second for two cases. The SABC_SD and SVNS_SD have ranked first for 2 out of 10 instances, respectively. The SGA_SD has a bad rank for most instances. Hence, the SPSO_SD outperforms its peers in solving the concerned problems.

Figure 17. The rank of Nemenyi post-hoc test.

Figure 18. Friedman’s binary rank variance analysis.

Convergence analysis

In this section, we present curves depicting the convergence of four classical meta-heuristics. The results of cases with 47 tasks and 79 tasks are used, as shown in Figures 19 and 20. It is evident that the algorithms converge rapidly at the beginning and flatten out with the increasing computational time. SGA_GD algorithm gives the worst results. SVNS_SD has medium performance and more stability. SABC_SD fluctuates a lot during the convergence process. Compared with these algorithms, SPSO_SD has faster convergence and higher quality solutions. It can be observed that SPSO_SD has better efficiency and effectiveness than its peers.

Figure 19. Convergence curves of all compared algorithms for task 47.

Figure 20. Convergence curves of all compared algorithms for task 79.

Case study: aircraft engine disassembly

In the experimental part, the arithmetic instances include self-generated cases and some actual cases such as discarded cell phones for the case with 27 tasks, LCD TVs for the case with 36 tasks, laptop computers for the case with 47 tasks, and aircraft engines for the case with 51 tasks^[59]. The case with 51 tasks is a specific case provided by a domestic airport. Figure 21 is the disassembly priority diagram of the aircraft engine disassembly case in our project.

Figure 21. Precedence graph of the aircraft engine disassembly case.