Development of a Hybrid Model for a Single-Machine Scheduling Using Expert Systems and Search Algorithms: A Simulation Study

Job sequencing refers to the process of determining the most efficient order in which tasks should be processed at one or more workstations. Since workstations typically handle multiple tasks, effective sequencing is vital to minimizing costs associated with job delays and idle time at workstations [1]. Poor scheduling can lead to job congestion and long waiting queues, adding complexity and pressuring management to develop more effective scheduling solutions [2].

Job scheduling involves determining the optimal order for completing a set of jobs or orders on a single machine or a group of machines. The goal is to achieve the best possible outcome based on a specific objective [3]. By establishing an optimal sequence, it is possible to calculate start and end times for each job, along with key performance metrics for both jobs and machines. Efficient scheduling is essential for optimizing resource use, meeting customer requirements within designated timeframes, and reducing inventory levels [4].

In this context, a variety of priority sequencing rules or heuristics have been used to determine the sequence in which jobs can be processed at workstations. These rules guide decision-making regarding the allocation of workstations for further processing. The use of priority sequencing rules offers advantages, as they integrate current knowledge of operational conditions into scheduling processes [5]. The performance of a given sequence generated by a priority sequencing rule is assessed using key performance indicators, such as average job completion time, average number of jobs in the system, mean job tardiness, and the number of delayed jobs. Selecting the most appropriate sequencing rule for job processing presents a complex challenge, and no single rule can be universally regarded as the best option for all scenarios [6].

Thus, from a managerial decision-making perspective, a detailed method for selecting the optimal sequencing rule is essential. The chosen methodology should account for the problem's complexity by explicitly considering multiple criteria, leading to more informed and improved decisions. MCDM techniques address these requirements by structuring complex problems and facilitating the evaluation of multiple criteria simultaneously [7].

Despite the potential benefits of integrating MCDM techniques with sequencing rules, there has been limited research exploring this hybrid approach. Only a few studies have investigated the effectiveness of combining MCDM methods with priority sequencing rules [8]. This research gap presents an opportunity to examine the benefits of these hybrid methodologies for optimizing job sequencing across various contexts. By leveraging MCDM techniques, which allow for the explicit consideration of multiple criteria, and incorporating them into sequencing rule selection, researchers can enhance the decision-making process and improve the performance of job sequencing systems. Therefore, further exploration and empirical validation of the approach integrating MCDM with sequencing rules are necessary to advance understanding and practical applications in this area.

Classic scheduling rules have been offered to address scheduling problems. Some scenarios, however, frequently fail to perform well when numerous competing requirements are involved. As real-world scheduling problems get more complicated, hybrid approaches combining MCDM with metaheuristic algorithms like Genetic Algorithms (GA), Simulated Annealing (SA), and TS have grown in popularity [1]. These methods aim to integrate the qualities of two frameworks: MCDM techniques provide a systematic mechanism for evaluating and ranking, whereas metaheuristics methods like TS are used to refine and improve initial solutions.

Most previous studies have focused on finding solutions using traditional scheduling rules and deciding how to arrange these rules best, either manually or using mathematical models based on a single objective function by choosing one of the performance criteria. The main objective of this research is to create a more efficient framework for tackling single-machine scheduling problems by combining hybrid MCDM methodologies and meta-optimization methods. The goal is to handle the issues of balancing several conflicting performance criteria by ranking these rules based on their performance across six key criteria: total flow time, total delay, number of delayed jobs, maximum delay, average tardy, and average weight of tardy jobs. Another major objective is to employ the best ranking rule from the MCDM evaluation as the initial solution for the TS algorithm. To improve scheduling results, the study applies a variety of TS search strategies, including job swapping, block swapping, job insertion, and block insertion.

Figure 1 illustrates the methodology adopted to achieve the objectives. Job parameters include processing time, customer importance, and due date. Calculations were made for eight different scheduling rules for 50 random JSSM scenarios. Hybrid MCDM was designed to analyze performance criteria, i.e., flow-time, total tardiness, maximum tardiness, number of tardy jobs, average tardiness, and average weight of tardy jobs. The best solution was then identified and used as the starting initial solution for the TS algorithm, which improves the solution in four methods. The resulted data was compared and discussed.

The assumptions used in this research are as follows:

$J:$ Number of jobs; $J=\left\{J_1, J_2, \ldots, J_{{n}}\right\}$

$O_i$ : Number of operations; $i=1$

$R_i$ : Release date; $\left\{R_1, R_2, \ldots, R_n\right\}=0$

$S_i$ : Setup time; $\left\{S_1, S_2, \ldots, S_n\right\}=0$

$C_i:$ Cost; $\left\{C_1, C_2, \ldots, {C}_n\right\}=0$

$P T_i:$ Processing time; $P T_j=\left\{P T_1, P T_2, \ldots, P T_n\right\}$

$D D_i$ : Due date; $D D_i=\left\{D D_1, D D_2, \ldots, D D_n\right\}$

$W_i:$ Customer importance; $W_i=\left\{W_1, W_2, \ldots, W_{{n}}\right\}$

First-come, first-served (FCFS), sometimes known as first in, first out (FIFO), is the simplest work scheduling algorithm. It schedules jobs in the order they entered the ready queue. The average waiting time is not always the shortest, and throughput can be low because lengthy jobs might overwhelm the entire workload, forcing short jobs to wait for an extended period, and making it difficult for this system to fulfill deadlines.

Last-come, first-served (LCFS), also known as last in, first out (LIFO), reverses the previous rule by processing jobs in the opposite order they were received. This method can be irrational and has numerous disadvantages when it comes to deadlines.

Shortest Processing Time (SPT), also known as Shortest-Job-Next (SJN) or Shortest Job First (SJF), is a non-preemptive scheduling policy that requires work to be done based on the SPT. In other words, the jobs that have the shortest execution time are prioritized to start first. This rule is effective since it is simple and reduces the average length of time that each job must take to finish. However, if short jobs are introduced regularly, they may starve jobs that can take a long time to complete. Another drawback of using this algorithm in many industries is that the total execution time of a job must be known before execution.

Longest Processing Time (LPT), also known as Longest Job Next (LJN) or Longest Job First (LJF), is a scheduling system that arranges jobs so that each subsequent job has a shorter processing time than the previous one. When the machine is freed, the longest job ready at that time can begin working. This regulation increases the work in progress and may lead numerous short jobs to miss their deadlines.

EDD, earliest deadline first, or shortest deadline first, is a real-time scheduling method that prioritizes activities. When a scheduling event occurs (a job completes, a new job is released, etc.), the queue is searched for the process closest to the deadline, which becomes the next process scheduled for execution.

Least Slack Time (LST), also known as least slack first, is a dynamic priority scheduling technique. It prioritizes jobs depending on slack time, which is the amount of time remaining after completing a job if it begins now. It is mostly used in systems with several operations.

Priority scheduling: it is focused on prioritizing the jobs or the customers with the highest relevance or value and then moving down to the lowest. The disadvantage with this method is that it does not take into account delivery time, which can result in a substantial total delay.

Critical Ratio (CR): the CR scheduling rule determines the CR by dividing the total time remaining to the deadline by the total production time remaining. Priority is given to items in the production cycle with the smallest CR.

Flow time (FT) refers to the amount of time it takes for a job to be processed. This includes the time from when the job is entered until when it is done, which also means that it concerns all the jobs that were completed before this current job.

Tardiness for each job is the difference in value between the completion time and due date, which is deemed zero if the value is negative. However, total tardiness (TT) is the aggregate of all jobs’ tardiness.

where, $T_i$ represents the tardiness of job $i, C_i$ is the completion time of job $i$, and $D_i$ is the due date of job $i$.

Number of tardy jobs (NO. TJ) refers to the number of jobs that are late, which is the count of jobs whose completion time exceeds delivery time.

Maximum tardiness (MAX T) refers to the maximum value of tardiness among all the tardy jobs.

Average tardiness (AVG T) describes the median delay of the tardy jobs.

Average weights of tardy jobs (AVG W) is the mean weight of the jobs that their completion time is bigger than the due date.

MCDM is a strong analytical framework that helps in evaluating and prioritizing multiple, often conflicting, criteria in a decision-making process [9], [10]. In complex decision scenarios, where qualitative and quantitative factors are involved, MCDM provides a structured approach to the assessment of alternatives to optimize the decision outcome [11], [12]. MCDM uses techniques such as AHP in systematic analyses by the decision-makers, which include trade-offs among criteria [13], [14]. It is, therefore, an indispensable tool in decision-making within diverse fields, including engineering, management, and public policy, toward more informed and transparent decisions [15], [16].

This study employed two MCDM techniques: the AHP and the EDAS. The AHP was used to evaluate the six criteria and assign weights to them in order to estimate the relative importance of each criterion over another in the decision-making process. As for the EDAS, the distance between the criteria was utilized to bring the values of the criteria closer to each other, and the rules were then ranked based on this approximation.

The AHP is a mathematical and psychological strategy for organizing and analyzing complex decisions, as well as a precise approach to quantifying decision criteria weights. The analytic hierarchy approach was developed in the 1970s by Thomas L. Satty, who collaborated with Ernest Forman to create the Expert Choice program in 1983 [17]. Since then, it has been extensively researched and refined. The process is divided into three parts: the ultimate goal or problem to be solved; all feasible solutions, known as alternatives; and the criteria used to evaluate the alternatives. The AHP provides a rational framework for reaching a desired decision by identifying its criteria and alternative options.

Specialists and decision-makers use a customized questionnaire to compare the relative importance of two factors at a time. The analytic hierarchy procedure translates these opinions into numerical values that can be compared to all possible criteria. This ability to measure distinguishes the AHP from other decision-making techniques. The final part of the process involves calculating numerical priorities for each of the different possibilities. These numbers represent the most desirable options, based on the values of all participants in the evaluation.

AHP is extremely useful for making decisions for complex, high-stakes problems. It stands out from other decision-making techniques because it measures criteria and options that are traditionally difficult to measure with numbers. Rather than describing the “right” decision, AHP assists decision-makers in finding the values that best fit their understanding of the problem. Involving all stakeholders is critical since various specialists can weight criteria differently. AHP also differs from classic surveys or questionnaires because it eliminates bias from the decision-making.

One of the most essential steps in the hierarchy is the binary matrix, which is often used to represent the preferences of criteria for one another and was utilized in this study to calculate the weights of criteria by comparing them to the others.

The steps are as follows:

Step 1: The criteria to be evaluated and their numbers were defined. The numbers represent the size of the binary matrix, which in this case was 6$\times$6.

Step 2: The scale below was used to compare each pair of criteria, determining which is relatively more important than the other and to what extent it is preferred. The gray cells on the top are the inverse of the white cells at the bottom (Table 1).

Step 3: The summation of factors was calculated for each criterion and the total of these values was found (Table 2).

Step 4: The weights were determined by following the equation, as shown in Table 3:

The EDAS is an MCDM ranking mechanism that is particularly useful for evaluating and finding the rank of alternatives that have multiple weighted criteria [18].

The following steps were taken using the EDAS method [19]:

Step 1: The criteria and the alternatives were determined, which were eight rules and six criteria in this case.

Step 2: Each criterion was categorized as beneficial (where higher values desired) or non-beneficial (where lower values desired). In this case, they were all non-beneficial.

Step 3: A decision matrix was prepared and the average value of each criterion was calculated for the alternatives, as shown in Table 4.

where, $i$ refers to criteria, and $j$ refers to alternatives.

Step 4: Positive and negative distance from average determines how much better or worse the alternative is compared to the found average for each criterion. In other words, the positive distance is calculated by subtracting the value of alternative ($n$) at criterion ($x$) from the average of criterion ($x$), where $n$ and $x$ represent a specific alternative and criterion. If the difference is larger than zero, it is divided by the average value and multiplied by the weight percentage for this specific criterion (which was previously determined using AHP). If the difference is less than zero, the value is set equal to zero (Table 5).

If criterion is beneficial, then

If criterion is non-beneficial, then

However, for negative distance, the average of criteria ($x$) is subtracted from the value of alternative ($n$) at criterion ($x$). If the difference is greater than zero, it is divided by the average value, which is then multiplied by the weight percentage for this specific criterion. Otherwise, the value is returned to zero (Table 6).

If criterion is beneficial, then

If criterion is non-beneficial, then

Weighted values were calculated by multiplying the weight percentage per each criterion by $P D A_{i j}$ and $N D A_{i j}$, as shown in Table 7 and Table 8.

The summation of $W P D A_{i j}$ of each alternative value was calculated as follows:

The highest values of $S P_i$ and $S N_i$ were extracted and normalized values of $N S P_i$ and $N S N_i$ were found:

The values of $N S P_i$ and $N S N_i$ were normalized, as shown in Table 9.

Finally, the ranking was found by arranging alternatives in descending order based on $A S_i$ values.

TS is a metaheuristic optimization local search method that solves combinatorial problems by first implementing an initial solution and then enhancing it by making minor adjustments (or “moves”) to the present solution and examining surrounding alternatives. The quality of a neighborhood is important since it influences the possibility of a local search. The chosen TS method, Tabu list, and aspiration criteria influence the algorithm's decision on which neighborhood to explore and which moves to consider, allowing it to avoid redundant or low-quality solutions. TS enables the algorithm to accept non-improving moves temporarily to escape from local optima and explore new sections of the solution space. To do this, the search employs a short-term memory structure (Tabu list) that retains recently visited solutions or movements (or characteristics of those solutions) to keep track of forbidden moves and prevent the algorithm from returning to these solutions for a certain number of iterations. However, the Tabu list is not absolute; the aspiration criterion is a rule that permits certain moves, even those on the Tabu list, to be reconsidered under certain situations. The search constantly improves the solution by testing new moves, updating the Tabu list, and applying aspiration criteria, and it will stop when a preset condition is fulfilled, such as reaching a maximum number of iterations, a time restriction, or no further improvement is discovered after a particular number of iterations.

TS steps are as follows:

Step 1: Let $S$ be the set of all potential solutions.

Step 2: An initial solution $s_o$ was adopted, with $s_{\text {current}}=s_o$.

Step 3: The objective function $f(s)$ was defined to evaluate the quality of the solution $s$, aiming to minimize the solution and find $S^*$, with $f\left(s^*\right) \leq f(s)$.

Step 4: The neighborhood function $N\left(s_{\text {current}}\right)$ was defined.

Step 5: Iteration $k$ and $k_{\text {max}}$ were defined.

Step 6: The best solution was initialized and found $s^*=s_o$.

Step 7: The Tabu list $T=\left\{s_1, s_2, s_3, \ldots, s_i\right\}$ was established, where $s_i$ is the recently visited solution, and $l$ is the tenure length.

Step 8: The objective function for each solution in the neighborhood $f\left(s^{\prime}\right)$ was evaluated, where $s^{\prime}$ indicates that it is Tabu and cannot be visited for $k$ number of iterations.

Step 9: The best non-Tabu solution was selected from the neighborhood $s_{\text {best}}$.

Step 10: After setting $s_{\text {current}}=s_{\text {best}}$, the best-know solution can be updated if improvement is found $f\left(s_{\text {current }}\right) < f(s)$.

Step 11: After adding solutions to the Tabu list, the oldest entry can be removed if $l$ exceeds the maximum length specified.

Step 12: The steps should be repeated until a stopping criterion is met, such as a maximum number of iterations, a time restriction, or no improvement in the range of the set number of iterations.

TS is often applied to problems such as scheduling, routing, and assignment. Below is a breakdown of what are called operators, techniques, or methods used in TS for solving job scheduling problems.

Job swapping: It refers to exchanging two jobs in the initial solution. For example, as for the jobs $\left\{J_1, J_2, J_3, J_4, J_5, J_6, \ldots, J_n\right\}$ in a series, exchanging jobs would swap the positions of two jobs, such as switching $J_2$ and $J_3$, so that the schedule becomes $J_1, J_3, J_2, J_4, J_5, J_6, \ldots, J_n$. This method is used to investigate adjacent solutions by determining whether changing the placements of two functions improves the objective function which is the scheduling performance (by minimizing the six criteria).

Block swapping: It is similar to job swapping, except that it entails swapping a block that contains more than one job with another block. For example, as for jobs $\left\{J_1, J_2, J_3, J_4, J_5, J_6, \ldots, J_n\right\}$ in a sequence, swapping block $\left\{J_5, J_6\right\}$ with block $\left\{J_1, J_2\right\}$ may improve the solution, making the solution $\left\{J_5, J_6, J_3, J_4, J_1, J_2, \ldots, J_n\right\}$. Blocks can have more than two jobs, and this TS method is effective when tiny modifications do not result in considerable improvements.

Job insertion: It involves removing a job from its current position and inserting it in a different position in the sequence. For example, for jobs $\left\{J_1, J_2, J_3, J_4, J_5, J_6, \ldots, J_n\right\}$, removing $J_3$ from its current position and inserting it after $J_6$ in the sequence makes the solution $\left\{J_1, J_2, J_4, J_5, J_6, J_3, \ldots, J_n\right\}$. This procedure offers more comprehensive schedule alterations by moving one job to a more optimal position.

Block insertion: This method is similar to inserting jobs, but entire blocks are removed and inserted at different locations within the sequence. For jobs $\left\{J_1, J_2, J_3, J_4, J_5, J_6, \ldots, J_n\right\}$, removing $\left\{J_4, J_5\right\}$ from their current location and inserting it after $J_1$ in the sequence results in $\left\{J_1, J_4, J_5, J_2, J_3, J_6, \ldots, J_n\right\}$. This method is useful when a group of jobs has to stay together.

Simulation study refers to the use of a computational model to simulate the behavior or the performance of a system under various parameters. The purpose of using a stochastic simulation (random) is to have different results due to the randomness of selecting different values of the parameters, which can lead to a better understanding of how the system behaves under these multiple scenarios and improve the processes.

To demonstrate the proposed steps, a large-scale project with a capacity of processing 50 jobs was considered. One machine must process these jobs in 30 different scenarios. A total of 1500 jobs that were generated by a simulation model select random numbers with pre-defined constraints and parameters, with job processing time from 1 to 20 days, delivery time from January 1, 2024, to March 30, 2025, and the weight of the job or customer value from a scale of 1 to 10.

Five professionals and academics in engineering project management completed a questionnaire to assess the weights of the criteria. The average of the individuals' evaluations was then taken, producing the binary matrix in Table 10 below.

Given the weights, the EDAS method was used to rank the rules, and all 30 case studies concluded that the EDD scheduling rule was the best way to organize the 50 jobs.

The EDD scheduling rule was chosen as an initial solution to improve scheduling performance in all cases using the TS algorithm.

The code was used to program TS via the Google Colab application. The steps are as follows:

Step 1: Input data was extracted, such as processing times, weights, due dates, and initial job sequence.

Step 2: A function was defined to evaluate the solution based on total flow time, tardiness, and number of tardy jobs.

Step 3: A function was defined to generate neighboring solutions by swapping, inserting jobs, or moving blocks of jobs.

Step 4: As for implementation of the TS algorithm, the best solution and Tabu list were initialized. For a fixed number of iterations, after generating neighbors, the best neighbor not in the Tabu list was evaluated and selected. After updating the best solution if the neighbor improves the result, the selected neighbor was added to the Tabu list, ensuring its size limit.

Step 5: The TS was executed using different methods (job swapping, block swapping, job insertion, block insertion).

Step 6: The results were output after the completion of the search process.

The above programming gives the results of TS scheduling with four Tabu methods presented previously (job swapping, block swapping, job insertion, and block insertion) for the 50 cases included in the input process. The program then compares the performance of the TS scheduling outcomes to the initial solution (EDD), which was chosen primarily because it outperformed the other scheduling rules.

The TS produced results for six performance criteria across all the simulated scenarios. Some methods outperformed others in the number of improved cases on some criteria, while others outperformed others. For one criterion, the initial solution remained the one with the highest number of cases with the best solution. This means that the solution did not improve on the Tabu.

JSSM was thoroughly simulated by creating 50 job determinants for 30 randomly chosen scenarios. Each work had a processing time, customer value, and a due date assigned. A separate table was utilized to schedule the jobs according to ranking rules. The rules were reviewed using the MCDM. The EDD scheduling rule proved to be the most effective in all cases. This is due to the fact that EDD is usually beneficial for reducing delays, while four of the six evaluation criteria are delay-related, with a combined weight of about 70% according to the binary evaluation matrix. Using Tabu, the model represented four Tabu approaches in comparison to the initial solution. The outcomes of each criterion improved. The values in Table 11 represent the number of cases, out of 30, in which method j has the best result for criterion i. The table shows that the initial solution using EDD produces 30 better results in terms of the maximum tardiness. It also outperforms Tabu methods in the number of cases that produce a better result in the average tardiness and the average weight of tardy jobs criteria by 15 and 11 cases, respectively. However, it was discovered that the job swapping method produces the highest score in terms of flow time by improving the solution for 20 cases, while the total tardiness and the number of tardy jobs rank second.

Block swapping improves the solution and achieves acceptable results in the average tardiness by improving the solution in nine cases, ranking second after the initial solution results, while the improvement in the solution is regarded as minor in the remaining five criteria. The job insertion method exceeds all other methods in terms of total tardiness and number of tardy jobs with 15 and 17 cases, respectively, and ranks second in terms of average weight of tardy jobs with seven cases. The block insertion method showed its highest improvement in the average weight of tardy jobs criterion with only four cases, ranking sixth overall.

In this study, hybrid MCDM methods based on AHP, weight assignment, and EDAS were created to evaluate the eight scheduling rules used for JSSM and select the optimal rule. The TS model worked in four ways to improve the solution and provided better solutions to the performance criteria. Tabu's results and the initial solution were compared to see how much the performance criteria were improved. The model provides flexibility in changing the proposed performance criteria (flow time, total tardiness, number of tardy jobs, maximum tardiness, average tardiness of tardy jobs, average weights of tardy jobs) and their weights based on the knowledge of experts to obtain new rankings for the rules. It also allows modification to the values of the three parameters (processing time, delivery time, job weight or importance) to generate additional case studies and thus varied results provide a better understanding and accuracy for the simulation study.