In this section, the original IWD (OIWD) is customized to solve SOJSSP and MOJSSP. An overview of the OIWD algorithm is first given in section “Overview of the OIWD Algorithm.” The schemes for improving the OIWD algorithm are presented in section “Schemes for Improving the OIWD Algorithm.” A brief description of the disjunctive graph is then given in section “Problem Representation Using Modified Disjunctive Graph” as the IWD algorithm for scheduling is represented on the disjunctive graph in this research. The enhanced IWD algorithm, EIWD for SOJJP, is presented in section “Enhanced IWD Algorithm (EIWD) for SOJSSP,” and the proposed MOJSS-IWD algorithm for MOJSSP is introduced in section “Modified IWD Algorithm Based on Scoring Function for MOJSSP.” The MOJSS-IWD algorithm is based on the IWD algorithm and a score function is embedded into its local search process.

Overview of the OIWD Algorithm

The IWD algorithm is inspired by the movement of natural water drops which flow in rivers, lakes, and seas. It is a population-based meta-heuristics where the IWDs construct a better solution through cooperation with each other. This algorithm can be applied to solve optimization problems (Shah-Hosseini 2009a). As pointed out by Shah-Hosseini, a stream can find an optimum path considering the conditions of its surroundings to reach its ultimate goal, which is often a lake or a sea. In the process of reaching for the destination, the water drops and the environment react to each other as the water drops move through the river bed. The water drops can change the environment (river beds) in which they are flowing; the environment can also influence the moving directions of the water drops. The gravitational force of the earth powers the IWDs moving toward the destination. If there are no barriers or obstacles, the IWDs will move in a straight path to the destination. However, in the real scenario, as there are different types of obstacles when IWDs are forming their paths, the real path of the IWDs may be different from the ideal path. In a river path, many twists and turns (meanders) can be observed. However, by considering the distance to the destination and the environmental constraints, the constructed path seems to be an optimal one (Duan et al. 2008, 2009).
In the OIWD algorithm, the IWDs are associated with two attributes, namely, the amount of soil and the velocity of the IWDs. The velocity enables the water drops to transfer soil from one place to another. Faster water drops can gather and transfer more soil from the river beds. Besides, the velocity of the IWDs is also affected by the path condition. The amount of soil in a path has impact on the IWDs’ soil collection and movement. A path with less soil allows the IWDs to move faster along that path, and the IWDs can attain a higher speed and collect more soil from that path, while a path with more soil is the opposite.
In the IWD algorithm, the movement of IWDs from the source to the destination is performed in discrete finite-length time steps. When an IWD moves from one location to the next one, the increase in its velocity is proportional (nonlinearly) to the inverse of the soil of the path between the two locations, and the soils of the IWDs increase because the IWDs remove some soil from the path they travel. The soil increase is in inverse proportion to the time needed for the IWDs passing between the two locations. The time duration to travel from one location to the second location depends on the distance between these two locations and the velocity of the IWDs. In the OIWD algorithm, the undesirability of a path is reflected by the amount of soil in the path. When an IWD has to choose a path among several candidate paths, it would prefer an easier path, i.e., a path with less soil than with more soil. The IWDs select a path based on a probabilistic function. The IWD algorithm uses a parameterized probabilistic model to construct solutions, and the values of the parameters are updated in order to increase the probability of constructing high-quality solutions.
The IWD algorithm has been tested using several standard optimization benchmark problems. It can find good solutions for TSP (Shah-Hosseini 2007, 2009a), and it can also solve robot path planning (Duan et al. 2008, 2009), the n-queen puzzle (Shah-Hosseini 2009a), and the MKP (Shah-Hosseini 2009a, b) with optimal or near-optimal solutions.
In this research, the OIWD algorithm is further improved with five schemes; the rationale behind the proposed schemes is to increase the diversity of the solution space as well as improve the search quality of the IWDs. The detailed description of the schemes is given in section “Schemes for Improving the OIWD Algorithm.”

Schemes for Improving the OIWD Algorithm

As a meta-heuristic algorithm, IWD suffers from two problems, viz., (1) it has an earlier convergence and (2) the initial solution and the diversity of the solution space often affect its search quality. The OIWD algorithm is enhanced through five schemes to form the EIWD for solving SOJSSP and the MOJSSP-IWD to solve MOJSSP in this research.

(1) Scheme 1: Diverse Soil and Velocity Initialization

In the OIWD algorithm, all the edges are set with the same amount of initial soil, and all the IWDs have the same initial velocity. In the modified algorithm, the initial amount of soil of each edge is randomly set, and the initial velocity of every IWD is also randomly chosen. This different initial soil and velocity setting provides the modified IWD algorithm with a diverse initial solution space.

(2) Scheme 2: Conditional Probability Computation

When an IWD is at node i in the disjunctive graph, the probability of choosing node j is represented by pIIWD(j). The OIWD algorithm computes this probability based on the soil on the edges. In the EIWD algorithm, to increase the convergence speed of the IWDs, namely, the speed of finding a best path, the probability is computed based on the soil of the edges and the processing time pt(j) of the candidate nodes (operations). To further improve the diversity of the search process, a piecewise function (Eq. 1) is employed to determine this probability (conditional probability computation). A random number φdec ∈ (0, 1) is used to determine the method to be used for computing the probability. φdec is compared with φ0 = 0.5; the probability of choosing node j is determined by comparing the results of φdec and φ0. rn ∈ (0, 1) is a random number to add randomness to the probability. τ is a variable which represents the relative importance of the soil of the edge to the processing time of the next operation, its default value is 1, which indicates these two variables are equally important. The rationale behind the conditional probability computation lies in broadening the possible solution search space

(3) Scheme 3: Bounded Local Soil Update

The soil updating model is one of the most important components of an IWD algorithm. To make full use of the guiding information and controlling of the convergence rate of finding a path, a bounded soil-updating model is proposed. This model differs from the soil-updating model in the OIWD algorithm by applying a lower and an upper bound to the soil-updating process. Let Δsoilmax and Δsoilmin be the upper and lower bound values of the soil changes when the IWDs pass through any edge in the disjunctive graph. The lower bound (a small positive constant) prevents the algorithm from slow convergence, while the upper bound prevents the algorithm from getting to the local optima too quickly. More precisely, the edge (i, j) soil updating and IWD soil updating use the following formulas:

Problem Representation Using Modified Disjunctive Graph

To implement the IWD algorithm for SOJSSP and MOJSSP, the JSSP is represented as a modified disjunctive graph Gdis which resembles rivers as in the IWD algorithm. A disjunctive graph Gdis = < N, C, D > can be used to represent a JSSP (Yamada 2003; Balas 1969). A disjunctive graph Gdis has a node set N, a disjunctive edge set D, and a conjunctive edge set C. Each operation has a corresponding node in the node set N. Besides, N contains two dummy operations (source node and sink node) with zero processing time. For the conjunctive edge set C, it contains directed edges connecting the neighbor operations of the same job. Such edge links can represent the precedence constraints of the l operations of the same job. The disjunctive edge set D contains undirected edges which connect consecutive operations processed on the same machine. These edges are undirected ones against each other, which represent the unsolved precedence of the operations. Both the disjunctive edges and conjunctive edges emanate from the operation nodes, and their lengths represent the processing times of the operations where they emanate. Thus, the lengths of the outgoing edges from the same node are the same.
In the schedule construction process, one direction of the disjunctive edge pairs should be determined in order to change each undirected disjunctive edge to a directed conjunctive edge. In this research, the IWDs will follow the next node using the probability of the next node that is calculated using IWD algorithm. The processing order of all the conflicting operations that require the same machine is determined by fixing the directions of all the disjunctive edges and a complete schedule is obtained. The optimization objective is the length of the longest path (critical path) in the newly constructed graph. This path is acyclic with the source node as the start node and the sink node as the ending node. For a 3 x 3 job indicated in Tables 1 and 2, its disjunctive graph representation is shown in Fig. 1. There are two dummy nodes, namely, s and t, which represent the source node and the sink node, respectively. Each operation is represented by a node, and the nodes in one row form a job, e.g., the nodes in the first row (node 11, node 12, and node 13) represent job 1, and the node (operation) with number 12 (O12 for ease of representation) represents the second operation of job 1. The operations belonging to the same job are connected by the conjunctive edges according to their processing order. The first operation of each job is connected to node s, while the last operation of each job is connected to node t. The operations which are performed on the same machine are connected by disjunctive edges. For example, O12, O23, and O31 are connected by disjunctive edges as they are performed on machine 3.

In this research, the objective is to solve the SOJSSP and MOJSSP depicted in the disjunctive graph using the modified IWD algorithm. The disjunctive graph depicts the environment for the IWDs, and the IWDs flow on the edges of the graph. Each IWD travels on the graph gradually along the edges from source to sink. After the completion of the iterations, all the IWDs will reach the sink. The solutions are represented by the edges that the IWDs have visited.
The basic idea of the IWD algorithm is to set up a graph and let the IWDs travel through the graph. IWDs travel from a start node to a destination node. During the travel, the soils of the edges are modified as the IWDs pass through these edges. The soil and velocity of the IWDs are modified as well. To apply the modified IWD algorithm to SOJSSP and MOJSSP, a modified disjunctive graph is used. Figure 2 shows the modified disjunctive graph for the 3 x 3 job described in Tables 1 and 2.

Besides the edges in a standard disjunctive graph (as shown in Fig. 1), new edges are added (shown as dash edges). For each node (operation) Ox, all the operations that are possible subsequent to Ox in the schedule are identified. Dash edges are formed to connect Ox and the potential subsequent operations in the schedule. For example, the possible subsequent operations of O22 in a schedule are O11, O12, O13, O23, O31, O32, and O33, and O22 is connected to O31, O11, O12, and O33 by dash edges (for the rest of the operations, no dash edges are formed as they are already connected to O22.). Figure 3 shows the dash edges of O22.