The EIWD and MOJSSP-IWD algorithms have been implemented on a PC with an Intel Core 2 Duo L7700 1.8GHz CPU and 2GB RAM. Experiments have been conducted on the benchmark data for JSSP in the OR-Library (Beasley 1990); 43 instances were tested among which three instances (FT06, FT10, FT20) are designed by Fisher and Thompson (FT instances) (Fisher and Thompson 1963) and 40 instances (LA01-LA40) are designed by Lawrence (LA instances) (Lawrence 1984).

Experimental Evaluation of EIWD for SOJSSP

The parameters (with their values) used in the experiments are listed in Table 3. For the parameters, through experiments and theoretical study, some observations can be obtained. For NIWD, NIWD_iter, N'Breadth, N'Depth, and NBD, a larger value will result in better solutions but longer computation time. Trade-off values are obtained based on experiments for these parameters. For Nsize_tabu, experiments show that a Tabu list that is too large or too small will result in low-quality results. Niter_LS is set to be 3,000 as experiments showed that for most cases where the value is larger than 3,000, the results will not improve further, but the computational time is increased. The parameters in the last two rows of Table 3 ensure that the values of the velocity updated and the soil updated are changed in the same scale of magnitude as the original velocity and the original soil.

The EIWD algorithm is compared with the TS algorithm (Pezzella and Merelli 2000), GA algorithm (Gonc¸alves et al. 2005), and the PSO algorithm (Lin et al. 2010; Ge et al. 2008). Table 4 shows the comparison results for FT and LA test instances. TSSB, HGA-Param, HIA, and MPSO are the names of the algorithms from Pezzella and Merelli (2000), Goncalves et al. (2005), Ge et al. (2008), and Lin et al. (2010), respectively. In this table, the relative average deviation represents the ratio of the average deviation for TSSB, HGA-Param, HIA, and MPSO with respect to that of EIWD. EIWD can find 37 best known solutions among the 43 instances, and the optimal results are better than that of TSSB, HGA-Param, HIA, and MPSO. From Table 4, it can be seen that the results of EIWD is closest to the best known solutions. Its deviation is about 1.74 times smaller than TSSB, 6.70 times smaller than HGA-Param, 5.39 times smaller than HIA, and 2.36 times smaller than MPSO. Thus, EIWD can find better results as compared with the TS Algorithm (Pezzella and Merelli 2000), GA (Gonc¸alves et al. 2005), and PSO (Lin et al. 2010; Ge et al. 2008). It does not only find more best known solutions (BKS) but also results with a smaller average deviation.

Experimental Evaluation of MOJSSP-IWD for MOJSSP

Experiments have been conducted using the same test instances for MOJSSP, and the research results are compared with the research conducted by Suresh and Mohanasundaram (2006). The makespan (Cmax), tardiness (Ti), and the mean flow time (F¯) are considered in the experiments in this research. These three objectives are conflicting, and achieving good results with respect to one objective may degenerate the results with respect to the other objectives. Suresh and Mohanasundaram used Pareto archived simulated annealing (PASA) to solve the JSSP with the objectives of minimizing the makespan and the mean flow time of jobs. The schedules generated by PASA does not consider the tardiness (Ti) objective. Simultaneous consideration of the three objectives in this research is more challenging than considering two objectives in the case of PASA.

The parameters (with their values) used in the experiments to test MOJSSP-IWD for MOJSSP are listed in Table 5. The values of the parameters are set based on trial and error experiments and theoretical study. The experimental results for MOJSSPIWD are shown in Table 6. In Table 6, “NA” means “not applicable” and it indicates those cases where the number of schedules in the Pareto optimal set obtained by MOJSS-IWD is less than that obtained by PASA. There are a total of six test instances among all the 43 benchmark instances in the category that “the number of schedules in the Pareto optimal set obtained from MOJSSP-IWD is less than that obtained from PASA.” For the rest of the 43 benchmark test instances (37 in total), the makespan and mean flow time of their schedules are summed up (Σ Cmax + F¯).  Among the 37 instances in Table 6, the MOJSSP-IWD algorithm outperforms the PASA algorithm for 27 test instances in terms of the quality of the Pareto non-dominated set, and the PASA performs better than MOJSSP-IWD for 10 test instances. MOJSSP-IWD outperforms PASA when the sum (Σ Cmax + F¯) for the Pareto non-dominated set generated from MOJSSP-IWD is smaller than that generated from PASA.
In general, the MOJSSP-IWD algorithm can generate better results than PASA. When the three objectives (makespan Cmax, tardiness Ti, and mean flow time F¯) are considered such that the problem becomes more challenging, it becomes more obvious that MOJSSP-IWD is a promising approach for solving the multi-objective scheduling problem.