The open shop scheduling problem involves a set of activities that should be run on a limited set of machines. The purpose of scheduling open shops problem is to provide a timetable for implementation of the entire operation so that the total execution time is reduced. The tasks scheduling problem in open shops is important in many applications due to the arbitrariness of the processing sequence of each job and lack of a prioritization of its operations. This is an NP-hard problem and obtaining an optimal solution to this problem requires a high time complexity. Therefore, heuristic techniques are used to solve these problems. In this paper, we investigate the tasks scheduling problem in open shops using the Bat Algorithm (BA) based on ColReuse and substitution meta-heuristic functions. The heuristic functions are designed to increase the rate of convergence to the optimal solution. To evaluate the performance of the proposed algorithm, standard open shop benchmarks were used. The results obtained in each benchmark are compared with those of the previous methods. Finally, after analyzing the results, it was found that the proposed BA had a better performance and was able to generate the best solution in all cases.
Notes
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
The scheduling and sequencing of operations is, in fact, the optimal allocation of limited resources to activities over time [1]. Due to its importance and practical application, extensive research has been carried out in this area since the early 1950s. Suppose machine (\(i = 1, 2\), ..., m) must process n work (\(j = 1, 2\), ..., n). A schedule is the allocation of time periods for processing these jobs on machines. Any schedule can be displayed on a Gantt chart [2]. An efficient and suitable schedule will lead to increased profitability, reduced costs, reduced time required to accomplish activities and winning the customers’ confidence. In most manufacturing factories and service companies, timely delivery of customers’ orders or timely delivery of services is important. Costs of delay in these problems not only lead to customer loss, but it also reduces the credit of service companies or manufacturing factories. Therefore, attention to scheduling problems is important in many management issues and planning principles. Workshop environments including workshop jobs and workshop flows are used in many industrial and service processes [3‐5]. An open shop scheduling problem (OSSP) environment is a workspace environment in which there is no operation-dependent sequence. Therefore, it has a wider solution space than other workspace environments. As a result, less attention has been paid to the open shop problem (OSP) compared to other workspace environments [6]. The OSSP was first introduced in major car repair garages [7]. It has other applications, most notably quality control centers, semiconductor manufacturing centers, teacher classroom assignments, inspection schedules and satellite communications [8‐10]. Scheduling problems are one of the most important issues of production planning. Scheduling is a resource allocation process limited to activities over time [11]. Scheduling problems are formulated in the form of machines and jobs (activities), where machines represent resources and jobs represent activities that need to be done using these resources [12]. The OSP is one such problem. In fact, it is such that there are a number of machines and a number of jobs in the workshop. Each job includes a number of operations and each operation must be processed on a predetermined machine. However, the important point that distinguishes this from the rest of the problems is that the ordering of operations of a job is not predetermined. Provided that the order of operations had been important, we had a job shop problem (JSP) [13]. Therefore, any arbitrary order can be considered for operations of a job. For this reason, the formulation of the OSSP is more complicated than the job shop scheduling problem (JSSP) and the flexible job shop scheduling problem (FJSSP) problems. In the OSP, each machine can process at most one job at a time, and each job can also be processed at most on a single machine at a time [14‐16].
In recent years, the application of mathematical models to finding the optimal solution (OS) of the scheduling problems has attracted the attention of many researchers. In this regard, many studies have been done on modeling the workshop jobs and workshop flows. In addition, formulation of the OSSP is less attractive to researchers. Since an increase in the number of machines (\(m\geqslant 3\)) turns the problem into an NP-hard one [7, 17, 18], heuristic and meta-heuristic algorithms have been used in most studies on the OSSP. Tautenhahn and Woeginger [19] studied the OSSP with regard to unit-time operations so that the availability of resources varies over time in their problem. They developed polynomial algorithms for multiple target functions such that the number of machines, the number of resources and the demand for each resource were limited. They were able to define a boundary between easy and hard versions of the problem by proving that they are NP-hard problems. The most important studies were carried out on heuristic algorithms by Brasel et al. [20] who presented a comparative study of heuristic algorithms for OSP aimed at minimizing the average flow time. They made comparisons for problems with up to 50 jobs and 50 machines. They showed that if the number of jobs is higher than machines, the algorithm solving time is far less. Among the meta-heuristic algorithms, Alcaide et al. [21] developed a tabu search (TS) algorithm for solving the OSP with the goal of minimizing the makespan. They tested their proposed algorithm on random data of varying dimensions. Liaw [22] proposed a hybrid genetic algorithm (HGA) to solve the OSSP aimed at minimizing the makespan. His proposed algorithm has been developed by adding a local optimization function to genetic algorithm (GA). The optimization function is based on TS algorithm. He used his proposed algorithm to solve random problems and the benchmark problems present in the literature up to 20 jobs and 20 machines, and in some cases, he was able to deliver results close to optimal values. Blum [23] presented an ant colony algorithm (ACO) using the beam search process and was able to deliver outstanding results for the problem. Huang and Lin [24] proposed a new honeybee optimization algorithm for the OSP considering the idle time. This method reduced time and cost based on the fact that the less the idle time, the less the makespan. Hosseinabadi and Ahmadizar [25] proposed a HGA for the OSSP with the goal of minimizing the maximum completion time of the jobs. In this algorithm, a special intersection operator is used to maintain the order of the machines and also a strategy is used to avoid the search for unnecessary responses in the jump operator. Chen et al. [26] presented the parallel open workshop scheduling by providing an approximate algorithm. Each job consists of two independent operations each of which is processed by one of the m pairs of parallel machines. The goal was to minimize the makespan of the last job. Naderi and Zandieh [27] studied the problem of open workshop planning without intermediate buffering. The paper presents an easy-to-use procedure of encryption and decryption frameworks for nonstop open shop problems (NS-OSP). The proposed meta-heuristic operators are designed to create a problem encryption framework. Bai et al. [28] explored the static and dynamic versions of the flexible open shop problem (FOSP) to minimize the makespan of the last job. They used the general dense scheduling algorithm (GDSA) for solving problems in a larger scale aimed at accelerating convergence. Tanimizu et al. [29] presented a scheduling method for solving the open workshop problems including disassembly and post-processing operations. A co-evolutionary algorithm was designed to improve the sequence of operations and product loading. Evolutionary algorithms have been widely used not only in the OSP, but also in all issues related to scheduling. For example, Gao et al. [30] proposed a new method based on the bee colony algorithm (BCA) that solves the FJSSP. In this method, the uncertainty of the processing time is modeled with a parameter called fuzzy processing time. Defined goals include the minimization of two metrics, fuzzy completion time and fuzzy machine workload. The proposed algorithm, IABC, can be a part of a decision maker’s expert system in management and scheduling. In another study, Zhao et al. [31] proposed a new method based on the water wave optimization algorithm (WWOA) to solve the no-wait flow shop scheduling problem (NW-FSSP). The researchers devised a discrete version of the WWOA that has the ability to solve the flow shop scheduling problem (FSSP). In this method, a crossover operator is also defined besides the main operators of the WWOA. The crossover operator is used to prevent getting caught in local optima. Marichelvam et al. [32] solved the multistage hybrid FSSP using the bat algorithm (BA). Hybrid flow shop (HFS) is a generalization of the product deployment problem including several machines. Oulamara et al. [33] solved the two-machine OSSP. They considered the processing time of an operation as a combination of two times, preparation time and runtime. The preparation time period comes before the runtime period on the machine and requires renewable resources. The authors were able to prove that various versions fall into the category of NP-hard problems. Zaher et al. [34] introduced a meta-heuristic method based on BA in order to optimize the workshop deployment problem. This algorithm works by reducing the start delay instead of reducing the makespan. In [26], parallel OSSP with the aim of reducing makespan is addressed. Due to the NP-hard nature of the problem, using approximate algorithms is suggested to solve the problem. Goldansaz et al. [35] addressed the multi-processor OSSP with some constraints such as independent setup time, process time and sequence-dependent removal time. They used a combination of imperialist competitive algorithm (ICA) and GA to solve the problem. It has been proven in [36] that, if a constraint is considered for machines’ load, three-machine proportionate OSP can be solved in O(n log n) time. If no constraint is taken into account, approximate methods can be used to solve the problem. Low and Yeh [37] defined the OSSP as an integer 0-1 programming model and then proposed a HGA with the aim of reducing the total delay of jobs and considered some constraints such as independent setup and dependent removal time. In [38], Lagrange expansion has been used to reduce the total quadratic completion time of small OSSP. In [21], an effective HGA named hybrid NSGA-II is proposed to solve the OSSP. In the proposed method, local search algorithm (LSA) is used to generate initial population. This method is used to solve medium and large problems. Results of the proposed method are compared with SPEA-II in terms of quality and diversity. Results indicated the superiority of the proposed method. An HGA with special operators is presented in [25] to solve the OSSP. Proposed crossover operator is able to eliminate the order in which jobs are performed on machines, and mutation operator avoids searching for additional solutions. The proposed method is a combination of iterative randomized active scheduling, dispatching index and lower bound.
Advertisement
There are many different versions of this problem which have their adjusted solution. One of the issues which can be added to this problem is priority. Some jobs have higher level of priority in comparison with others. This version of the problem has been addressed by an approximation algorithm. This method handles the process through a directed acyclic priority graph [39, 40]. Open shop scheduling problem or OSSP can be solved by other constraints. For example, predefined travel time between machines and setup times without any specific order. In order to tackle this problem, an innovative permutation model has been proposed to be used in variable neighborhood search. Evaluation of the algorithm on both random problems and standard benchmarks suggests that the innovative permutation method has the most positive impact on produced outputs [41, 42].
Some papers have focused on a solution for OSSP which can be run on a multiprocessor. Parallel executing of an algorithm could increase its productivity significantly. For example, in a paper a new method has been proposed. In this method, an innovative SS/PR meta-heuristic has been designed for the multiprocessor OSSP. Moreover, a distance function has been developed to show the difference between different solutions. Based on a standard benchmark, evaluating the algorithm shows gaining optimal solution in 7 cases and new upper bound in 18 other special cases [43, 44].
In this paper, we will solve the OSP for the first time using the bat meta-heuristic algorithm. Previous methods have some shortcomings in exploring problem space. Hence, we need a better algorithm in terms of exploration in order to tackle this problem. Since BA is a strong algorithm in both aspects of exploration and exploitation, it has been used in this article. The structure of the paper is organized as follows: in Sect. 2, the problem statement is described. Section 3 describes the bat algorithm. Section 4 presents the proposed algorithm. Simulation results and conclusions are presented in Sects. 5 and 6, respectively.
2 Problem statement
The OSSP is a matter of general task scheduling. The open shop is an NP-hard problem and solving it in polynomial time is not possible. In this case, there are n jobs and m machines. Each job contains m operations each of which must be run by a machine. The machine that must execute an operation is already specified. The order of the operations of a job is not important, but more than a single operation cannot be executed at a moment. The problem solution is generated as a matrix. Each row of this matrix shows the order of the jobs a machine should run. The following parameters are used to define the OSP:
n – number of jobs in the OSP,
m – number of machines in the OSP,
i – machine index in relations,
j – job index in relations,
\(op_{j,i}\) – \(Job_{j}\) operation that must be run on \(Machine_{i}\),
\(d_{j,i}\) – \(op_{j,i}\) runtime; this parameter is an input for the scheduling problem,
\(t_{j,i}\) – start time of running \(op_{j,i}\) on \(Machine_{i}\),
\(f_{i}\) – \(Machine_{i}\) idle time; the default value of this parameter is 0 when starting the scheduling for all machines,
\(assigned_{j,i}\) – equal 1 if \(op_{j,i}\) is selected for execution and equals 0 if \(op_{j,i}\) is not selected for execution. The default value of this parameter is 0 when starting the scheduling for all \(op_{j,i}\).
By reference to the above parameters, the runtime period will be equal to \(\left[ t_{j,i}, t_{j,i}+d_{j,i}\right] \). To calculate this time period, we must first calculate \(t_{j,i}\) as follows:
for all k where \(assigned_{j,k}=0\) and \(k\ne i\). In Eq. 1, variable i represents the machine chosen for calculation the scheduling. Machines are selected in a special order for scheduling. The choice of \(Machine_{i}\) for calculating in the current stage is done using Eq. 2. After selecting \(Machine_{i}\) and assigning \(op_{j,i}\) to it, \(assigned_{j,i}=1\) and \(f_{i}=t_{j,i}+d_{j,i}\).
If Eq. 3 is applied, the open shop scheduling (OSS) is a valid and acceptable scheduling. Equation 3 shows that more than one operation will not be executed at a single moment for any job.
The main purpose of solving the OSP is to reduce the amount of makespan. After calculating \(t_{j,i}\), Eq. 4 is used to obtain the makespan. In solving the OSP, we try to reduce the value of Eq. 4 function. In other words, this function is used as the target function in the problem.
Meta-heuristics usually inspired by nature and physical processes are now used as one of the most powerful methods to solve many complex optimization problems. BA is one of the nature-inspired meta-heuristic algorithms introduced by Yang [45]. This algorithm is based on the principles of bat life. Bats are the only mammals with wings that use echolocation for hunting prey. So far, it has been used to solve binary problems [46] and multi-objective optimization problems [47]. However, there are many discrete optimization problems that can be solved with existing meta-heuristics. So the goal of this paper is to provide a suitable form of bat algorithm for this type of problems. The BA is inspired by the traceability of small bats searching for hunt. So that small bats can hunt their prey and receive it in absolute darkness by emitting sound [48]. Three rules are used to develop this algorithm:
all bats use echolocation to detect distances and know the difference between food and progressive barriers,
bats fly randomly at velocity \(v_{i}\), at position \(x_{i}\), with fixed frequency of \(frq_{i}\) and different wavelengths \(\lambda \) and loudness of \(A_{0}\) for hunting prey. Also, they can automatically set emitted waves and sent pulse rates (\(r\in \left[ 0, 1\right] \)) according to proximity to their hunts,
given that loudness may vary in many different ways, we assume that loudness varies from \(R_{0}\) (maximum value) to \(R_{min}\) (minimum value).
According to the rules, the position \(x_{i}^{t}\) with velocity \(v_{i}^{t}\) for each virtual bat i in iteration t and frequency \(frq_{i}\) is calculated as follows:
where \(\beta \in \left[ 0, 1\right] \) is a random vector with uniform distribution, \(X^{*}\) is the best current position that is selected in each iteration and after comparison with the position of the virtual bats. Usually, frequency \(frq_{i}\) is selected between \(frq_{\mathrm{min}}=0\) and \(frq_{\mathrm{max}}=100\). In each iteration of local search, one solution is selected as the Best Solution (BS), and the new position of each bat is updated with a random step as follows:
where \(\epsilon \in \left[ -1, 1\right] \) is a random number and \(A^{t}=<A_{i}^{t}>\) is the average loudness of bats in iteration t. loudness \(A_{i}\) and pulse rate r are updated as follows:
According to the discussion above, BA is summarized in Algorithm 1.
×
The BA has the ability to achieve OS. The convergence analysis of the BA with the aid of the Markovian framework and dynamical system theory shows that this method will approach to the OS. The convergence of the BA is proved by both the Markovian framework and dynamical system theory. The empirical results of implementing this algorithm on well-known problem confirm its theoretical analysis [49].
4 The proposed algorithm
There are many applied solution methods developed for the optimizations problem in the literature such as exact methods, heuristics, meta-heuristics and so forth. Evolutionary algorithms are widely used to solve task scheduling problems. Given that the task scheduling problems are of an NP-complete type, the use of evolutionary methods can lead to a reasonable solution to this problem in a logical time. In this paper, a particle-based algorithm called bat is used to solve the problem. The BA is inspired by bats group movement to find food. In the following, how to formulate the task scheduling problem for the BA and the steps of the proposed algorithm are described.
4.1 Steps of the proposed algorithm
The proposed algorithm begins by creating some bats. Each bat has a random solution to the task scheduling problem. The best bat will be the base of the bats’ movement in the next round. The fitness of a bat shows its excellence. The bat fitness function represents the delivery time of the entire jobs in the scheduling problem. The discussion on how to calculate fitness is given in the following sections. After creating the bat and initializing the parameters of the algorithm, the main steps of the algorithm which simulates the movement of the bats begin. Algorithm 2 shows the general steps of the proposed BA for the task scheduling problem. In Algorithm 2, the fitness function is used to calculate the fitness of a bat which works on the basis of delivery time or makespan. Another function called ColReuse was used to calculate velocity of the bats. The concept of “velocity” has been redefined for this problem. The new definition is based on a heuristic similarity between bats. Also, the bats movement was done using the Substitution, Fold, FullReverse, Join, ShiftUp, and ShiftDown functions. These functions randomly change part of a solution. The InactionDel and SmallWalk functions are used to generate optimal solutions around the BS. The InactionDel function detects and eliminates the largest idle time between processors. The SmallWalk function creates a small movement in the bat by shifting two random jobs. The operation and pseudocode of these functions are described in the following sections.
×
4.1.1 Creating a bat
Given that the number of machines and jobs is equal in one of the benchmarks of this problem, all pseudocodes and examples are written for an equal number of machines and jobs without losing the whole problem. This is done only to simplify the description of the functions. Therefore, a bat is a random solution to a problem of a \(k\times k\) size. To generate random solutions, we first convert the solution space to a permutation of integers from one to \(k\times k\). Table 1 shows how this conversion works for \(k=3\). If we list all possible combinations of machines and jobs, we can create a sequence of numbers from one to \(k\times k\) by taking a sequence number. Any permutation of these numbers is a solution to the problem.
Table 1
Numbering the job and machine states
Sequence number creation
Machine
1
1
1
2
2
2
3
3
3
Job
1
2
3
1
2
3
1
2
3
Numbers
1
2
3
4
5
6
7
8
9
Equations 11 and 12 are used to calculate machine number and job number.
In these equations, k is the dimension of the problem (the number of machines and jobs) and “number” is a number in \(\left[ 1, k\times k\right] \). Equations 11 and 12 are calculated for all the numbers in the initial solution, and finally, a \(k\times k\) matrix is returned as the final solution. In Table 2, there is an example of a randomized solution to the problem for \(k=4\).
Table 2
A sample solution for \(k=4\)
Job number
Machine 1
1
3
4
2
Machine 2
3
2
4
1
Machine 3
1
2
3
4
Machine 4
4
1
2
3
4.1.2 Fitness function
The fitness value of a bat is equal to the amount of the makespan or the time it takes to complete all the jobs. To calculate this value, you must first schedule all the tasks. At the end of the scheduling, the exact time of the start and end of each task is determined. Therefore, the makespan value is simply quantifiable. The method of computing makespan is described in Eq. 4. In OSSP, each task is a set of subtasks that should not be run simultaneously. Therefore, the scheduling function postpones the start time of each subtask until the machine is empty and the associated subtasks are completed. Algorithm 3 shows the pseudocode of the scheduling function.
×
In Algorithm 3, \(MET_{1\times k}\) is the time each machine takes to be empty with an initial value of zero, \(PET_{1\times k}\) is the completion time of processing a job with an initial value of zero, duration is the time length of performing a subtask, start is the start time of a subtask, finish is the end time of a subtask, \(begin_{k\times k}\) is start time of subtasks of each machine, and \(end_{k\times k}\) is the end time of subtasks of each machine.
4.1.3 ColReuse function
To calculate the difference between a bat (\(x_{i}\)) and the best bat (\(X^{*}\)), a heuristic function called ColReuse was used. This function shows the maximum repetition of a number in a scheduling column. For a better understanding of the role of ColReuse in scheduling quality, look at the standard \(5\times 5\) example in Table 3. In this example, there are three different schedules, ColReuse 5, 4 and 3, respectively. By paying attention to the fitness of these schedules, we find that the higher the number of duplicate numbers in a column, the lower the scheduling quality. Using this function, we take the distance between the two bats as the ColReuse difference between them. The velocity of a bat in the proposed algorithm is equal to the difference between the bat (\(x_{i}\)) and the best bat (\(X^{*}\)). Therefore, the more the distance between the bat and the BS, the faster it moves to reach it.
Table 3
The effect of the ColReuse function
Solution
1
2
3
4
5
2
3
4
5
1
2
3
4
5
1
1
2
3
4
5
1
2
3
4
5
5
1
2
3
4
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
ColReuse
5
4
3
Fitness
1220
948
713
4.1.4 Substitution function
Substitution function creates a new permutation in a number of matrix rows. Rows are selected if one of their elements plays a role in increasing the ColReuse value. By creating a new permutation, ColReuse will drop and Fitness value will probably decrease. Table 4 shows a solution for a problem with 5 jobs and 5 machines, before and after substitution. The modified rows is marked in bold.
Table 4
Substitution performance
Before substitution
After substitution
Solution
3
2
1
5
4
3
2
1
5
4
1
3
4
5
2
4
1
5
2
3
1
2
5
4
3
2
4
3
1
5
1
3
5
4
2
3
5
1
2
4
5
4
2
3
1
5
4
2
3
1
ColReuse
3
2
4.1.5 Fold, FullReverse and join functions
In this section, three new functions used to move a bat are examined. Each of these functions in a particular way converts a solution to a new one. Therefore, the search in the solution space becomes more complete and the likelihood of finding a BS becomes greater. The Fold function chooses one of the rows randomly and reverses the top or bottom of that row completely. The FullReverse function reverses all the solution rows. The Join function selects a few rows in a solution and replaces them with the rows of a random bat. Table 5 shows an example of the performance of these functions. Modified parts are shown in bold.
Table 5
Performances of Fold, FullReverse and Join functions
Solution
After Fold
After FullReverse
After Join
4
2
1
3
4
2
1
3
3
1
2
4
4
2
1
3
3
2
1
4
3
2
1
4
4
1
2
3
3
2
1
4
3
4
2
1
1
2
4
3
1
2
4
3
2
1
4
3
1
3
2
4
4
2
3
1
4
2
3
1
3
4
1
2
4.1.6 ShiftUp and ShiftDown functions
The ShiftUp and ShiftDown functions choose one of the response columns randomly and then shift it up or down (depending on the function). After the shift operation, a duplicate number is created in some rows. To correct this state, the deleted number is replaced the number that has just entered. Therefore, a new and correct solution is obtained. Algorithm 4 shows the pseudocode of these functions.
×
The performances of ShiftUp and ShiftDown functions are illustrated in Table 6 (the columns are shifted and the modified elements are shown in bold).
Table 6
ShiftUp/Down performance
Solution
ShiftUp
ShiftDown
2
1
3
5
4
4
1
3
5
2
2
3
1
5
4
4
3
1
5
2
5
3
1
4
2
4
1
3
5
2
5
4
1
3
2
3
4
1
5
2
5
4
1
3
2
3
5
4
2
1
2
5
4
3
1
3
5
1
2
4
2
4
1
3
5
2
4
1
3
5
2
1
4
3
5
4.1.7 SmallWalk and InactionDel functions
All the functions described in the previous sections are meant for moving ordinary bats. However, the two functions, namely SmallWalk and InactiveDel, were intended for creating a place next to the best bat (\(X^{*}\)). Based on a \(1-r\) probability, a bat (\(x_{i}\)) is moved to that place. Pulse rate (r in Eqs. 9 and 10) has an initial value of 1 and decreases according to Eq. 13.
In Eq. 13, MaxGeneration is the maximum number of bats movements and t is the number of moves up to this moment. The diagram of this function, as depicted in Fig. 1, shows that at the beginning of the algorithm, the bats move to the area around the best bat with a little probability and they try to find the solution themselves. However, at the end of running the algorithm, most bats move to the area around the best bat and try to improve the BS.
Fig. 1
Pulse rate (r) modification for 50 generations
×
The InactionDel function was created with the aim of eliminating the greatest idle time between machines. This function finds the biggest gap between machines and shifts the machine tasks to the right. Therefore, the task that was delayed and created a gap moves from its place and another task takes this place and probably uses this idle time. The pseudocode of the InactionDel function is written in Algorithm 5.
×
The last function examined is the SmallWalk function. This function randomly selects two points of the matrix and moves its values. After moving, duplicate values may be created in two rows of the matrix. Duplicate values are deleted in the same way as performed for the Shift function. In the next section, the proposed method is implemented and the results are compared with those of the previous methods. In this section, functions designed to solve the OSP using the BA are described. After full description of these functions, it is necessary to determine how they will be used during the execution of the BA. Figure 2 shows the flowchart of the proposed algorithm.
Fig. 2
Flowchart of proposed algorithm
×
5 Simulation results
In this section, simulation results of the proposed algorithm (BA_OS) are presented. MATLAB programming language on a Laptop of Intel Core i7-4720HQ CPU 2.60GHz and 12.0 GB RAM is used to implement the proposed algorithm. In order to investigate the efficiency of the proposed algorithm for solving OSSP, this section presents scenarios including various jobs and machines for solving the problem using BA_OS algorithm; then, results are compared. Generated scenarios are divided into three groups according to the number of jobs and the complexity of the scenarios. Table 7 shows these scenarios with the number of jobs and machines. The parameters of the proposed algorithm are defined as follows: the number of bats that is set by the user for each problem. The number of generations or a number of bat movements are set by the user for each problem. Loudness (A) is set to 0.95. Pulse rate (r) emission starts from 1 and gradually (based on Eq. 13) reaches to 0 (Table 8).
Table 7
Generated scenarios
Data
Number of jobs
Number of machines
Display
Small-scale
4
4
\(4\times 4\)
data
5
5
\(5\times 5\)
Medium-scale
7
7
\(7\times 7\)
data
10
10
\(10\times 10\)
Large-scale
15
15
\(15\times 15\)
data
20
20
\(20\times 20\)
The BA_OS has been tested on Taillard criteria [50]. Tables 9 and 10 show the results obtained after applying any Taillard criteria [50] using the determined parameters. As seen, BA_OS achieves optimal solutions in most samples and achieved a relative advantage over compared algorithms.
Table 8
Parameter setting
Pulse rate (r)
Loudness (A)
Number of generations
Number of bats
Start from 1 and gradually reaches to 0
0.95
2000–3000
40–200
Comparison of the proposed algorithm (BA_OS) with other algorithms is presented in Tables 9 and 10. The proposed algorithm is compared with simulated algorithm (SA) [51], GA [52, 53] HGA [52, 54], neural networks [55], ant colony system (ACS) [56], cuckoo search (CS) [56] and cat swarm optimization algorithm (CSO) [57]. As seen, proposed algorithm could solve the problem well and compete with compared algorithms.
Table 9
Obtained results for benchmarks of size \(4\times 4\), \(5\times 5\), \(7\times 7\) and \(10\times 10\)
“N/A” is common in the table for the phrase not applicable
Table 9 shows the results for small size problems. In these problem sets, the optimal solutions are clear. Results of the proposed method show that all of the optimal solutions have been obtained by BA_OS. Table 10 lists the results for medium size problems. Solutions of proposed method indicate that in all problems (except \(20\times 20-8\)) the outputs are exactly equal to optimal solution. In comparison with other mentioned algorithms, this shows a reasonable enhancement. Large size problems have been tested in further tables.
The Gantt chart of a sample schedule for benchmark \(10\times 10-1\) is depicted in Fig. 3. The white pars of the chart show the gap times in each machine. Each color shows the operations of a particular job.
Fig. 3
Gantt chart of a sample schedule for benchmark \(10\times 10-1\)
×
5.1 Test problems
In this section, for further verification, the performance of the proposed BA_OS is evaluated using the benchmarks presented recently by Shamshirband et al. [6]. According to these benchmarks, some GA-based algorithms including DGA [37], SAGA [37], TSGA [37] and PGA [37] have been proposed to solve the problem which are compared to the proposed BA_OS. The main body of these methods is GA. The difference between these methods is in their local optimizations which are implemented by GA, SA (simulated annealing), and TS. The structure of TS and SA with a short memory is the same as classical forms (SA [59], TS [60]).The obtained results are presented in Tables 11 and 12 for small-sized (job size \(n = 3\) and 4; machine size \(m = 2\) and 3) and large-sized problems (job size \(n = 10\), 30 and 50; machine size \(m = 5\), 10 and 15), respectively. Since the results in Tables 11 and 12 include the BS and mean ones, the stability of the proposed method should be analyzed before investigating these tables. A multiple run of a plot and drawing of the plot box from the values obtained shows how far the outputs of that method are close to the mean value. As much as the generated values are closer to the mean value, the stability of that method is higher. Box plot of several run of the proposed method on six sample problems of large-scale size is shown in Fig. 4.
Investigating the values of Fig. 4 shows that in many cases, the outputs of the proposed method are close to the mean value. Therefore, the proposed method produces balanced outputs. Among six examined test problems, in three problems \(10\times 10-1\), \(30\times 5-1\) and \(30\times 15-1\) only one solution was distant from the average value, and the rest ones were within an acceptable distance from the mean value. The minimum value of each box plot represents the best produced solution. The details of the results for this benchmark are shown in Tables 11 and 12. According to the tables, the proposed method produces a better solution in most of the problems.
Table 11
Performance comparisons of the proposed algorithm and four GA-based heuristics (for small-size problems)
For a better comparison between the proposed method and the four previous methods, the results of these algorithms are shown in Fig. 5 in the form of box plots. The values of box plots are obtained from test problem \(50\times 5-1\). Results show that the results of the proposed method have the most similarity to the mean value. The PGA [6] method, with BS close to the proposed method, is much weaker in terms of sustainability. Other methods are much weaker than the proposed method in terms of both the BS and sustainability.
Fig. 5
Box plot of running of five different methods
×
6 Conclusion
The OSSP is a well-known scheduling problem with high application in industries. So, finding an optimal applicable scheduling in this environment would help in order to execute the best policy in industries. In this paper, a proposed bat algorithm is applied for solving OSSP. The aim of the proposed algorithm is to reduce production costs through minimizing makespan of such systems. Given that classical BA is presented for solving continuous problems and scheduling problem is a discrete problem, operations such as difference and bat’s movement are defined so that proposed algorithm can operate in a discrete environment. Optimization of random bats is done by two heuristic functions named: ColReuse and InactionDel. To evaluate the performance of the proposed algorithm, we tested it on standard benchmark and compared it algorithm with other algorithms. This benchmark includes small-, medium- and large-scale problems. Experimental results show that proposed algorithm obtained better results in all three categories. This improvement can be more obvious in larger production systems. For future studies, it is suggested to consider more real assumptions in the problem such as setup times and maintenance of the machines. Also, studying the uncertain nature of the parameters would make the mode more real.
Compliance with ethical standards
Conflict of interest
In the present work, we have not used any material from previously published. So we have no conflict of interest.
Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
