In this paper, a new meta-heuristics, viz., the IWD algorithm, is enhanced to solve SOJSSP and MOJSSP, where the JSSP is modelled as a modified disjunctive graph that resembles rivers in the IWD algorithm. In this research, the OIWD algorithm is improved by introducing five schemes, viz., (1) diverse soil and velocity, (2) conditional probability computation, (3) bounded local soil, (4) elite global soil update, and (5) a combined local search. The enhanced algorithms are the EIWD and the MOJSSP-IWD algorithms. The optimization objective considered for SOJSSP is makespan in this research, while MOJSSP with the consideration of three objectives, namely, the makespan, tardiness, and mean flow time, has been studied. The research goal for MOJSSP is to find a set of solutions in the form of alternative trade-offs in the Pareto optimal set, and a new method is proposed to generate the Pareto non-dominance set. A scoring function and a Pareto schedule-checking process are embedded in the MOJSS-IWD algorithm. Experiments have been conducted using 43 standard benchmark instances from the OR-Library to validate the effectiveness and efficiency of the enhanced algorithms.
Experimental results show that EIWD can generate better results by finding additional best known solutions and generate schedules with a smaller deviation from the best known solutions. Experimental results also indicate that MOJSSPIWD can generate better results in general. Considering that the three objectives have been explored, the question under study is very challenging, and MOJSSPIWD is a promising algorithm for solving MOJSSP.

References

Adibi MA et al (2010) Multi-objective scheduling of dynamic job shop using variable neighborhood search. Expert Syst Appl 37:282–287

Aytug H et al (2005) Executing production schedules in the face of uncertainties: a review and some future directions. Eur J Oper Res 161:86–110

Balas E (1969) Machine sequencing via disjunctive graphs: an implicit enumeration algorithm. Oper Res 17:941–957

Balas E, Vazacopoulos A (1998) Guided local search with shifting bottleneck for job shop scheduling. Manage Sci 44:262–274

Beasley JE (1990) OR-library: distributing test problems by electronic mail. J Oper Res Soc 41:1069–1072

Blum C, Sampels M (2004) An ant colony optimization algorithm for shop scheduling problems. J Math Model Algorithms 3:285–308

Chryssolouris G (2006) Manufacturing systems, theory and practice. Springer, New York

De Giovanni L, Pezzella F (2010) An improved genetic algorithm for the distributed and flexible job-shop scheduling problem. Eur J Oper Res 200:395–408

Duan H et al. (2008) Air robot path planning based on intelligent water drops optimization. Presented at the 2008 international joint conference on neural networks, IJCNN 2008, Hong Kong

Duan H et al (2009) Novel intelligent water drops optimization approach to single UCAV smooth trajectory planning. Aero Sci Technol 13:442–449

Fisher H, Thompson GL (1963) Industrial scheduling. Prentice-Hall, Englewood Cliffs

Garey MR et al (1976) The complexity of flowshop and jobshop scheduling. Math Oper Res 1:117–129

Ge H-W et al (2008) An effective PSO and AIS-based hybrid intelligent algorithm for job-shop scheduling. IEEE Trans Syst, Man Cybern, Syst Humans Part A 38:358–368

Giffler B, Thompson L (1960) Algorithms for solving production-scheduling problems. Oper Res 8:487–503

Gonc¸alves JF et al (2005) A hybrid genetic algorithm for the job shop scheduling problem. Eur J Oper Res 167:77–95

Hartmann S, Kolisch R (2000) Experimental evaluation of state-of-the-art heuristics for the resource-constrained project scheduling problem. Eur J Oper Res 127:394–407

Hong Z et al (2009) Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. Eur J Oper Res 194:637–649

Lawrence S (1984) Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques. PhD thesis, Graduate School of Industrial Administration (GSIA), Carnegie Mellon University, Pittsburgh

Lin T-L et al (2010) An efficient job-shop scheduling algorithm based on particle swarm optimization. Expert Syst Appl 37:2629–2636

Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manage Sci 42:797–813

Pan JCH, Han-Chiang H (2009) A hybrid genetic algorithm for no-wait job shop scheduling problems. Expert Syst Appl 36:5800–5806

Pezzella F, Merelli E (2000) A tabu search method guided by shifting bottleneck for the job shop scheduling problem. Eur J Oper Res 120:297–310

Reza HS, Saghafian S (2005) Flowshop-scheduling problems with makespan criterion: a review. Int J Prod Res 43:2895–2929

Seo M, Kim D (2010) Ant colony optimisation with parameterised search space for the job shop scheduling problem. Int J Prod Res 48:1143–1154

Sha DY, Lin H–H (2010) A multi-objective PSO for job-shop scheduling problems. Expert Syst Appl 37:1065–1070

Shah-Hosseini H (2007) Problem solving by intelligent water drops. Presented at the IEEE congress on evolutionary computation, CEC 2007, Singapore

Shah-Hosseini H (2009a) The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm. Int J Bio-Inspired Comput 1:71–79

Shah-Hosseini H (2009b) Optimization with the nature-inspired intelligent water drops algorithm. In: Santos WPD (ed) Evolutionary computation. Tech, Vienna, pp 297–320

Suresh RK, Mohanasundaram KM (2006) Pareto archived simulated annealing for job shop scheduling with multiple objectives. Int J Adv Manuf Technol 29:184–196

Vilcot G, Billaut JC (2008) A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem. Eur J Oper Res 190:398–411

Yamada T (2003) Studies on metaheuristics for jobshop and flowshop scheduling problems. PhD, Kyoto university, Kyoto

Zhang G et al (2009) An effective hybrid particle swarm optimization algorithm for multiobjective flexible job-shop scheduling problem. Comp Ind Eng 56:1309–1318