S. H. Niu: Department of Mechanical Engineering, National University of Singapore, Singapore
S. K. Ong, and A. Y. C. Nee: Mechanical Engineering Department, Faculty of Engineering, National University of Singapore, Singapore
97.1 Introduction
97.2 Problem Formulation
97.3 Solution Methodologies
Overview of the OIWD Algorithm
Schemes for Improving the OIWD Algorithm
Problem Representation Using Modified Disjunctive Graph
Enhanced IWD Algorithm (EIWD) for SOJSSP
Modified IWD Algorithm Based on Scoring Function for MOJSSP
97.4 Experimental Evaluation
Experimental Evaluation of EIWD for SOJSSP
Experimental Evaluation of MOJSSP-IWD for MOJSSP
97.5 Summary
References
Abstract
Job shop scheduling problem (JSSP) is a typical scheduling problem that aims to generate an optimal schedule to assign all the operations to the production equipments. JSSPs can be categorized into single objective JSSP (SOJSSP) and multiple objective JSSP (MOJSSP) based on the optimization objectives considered. SOJSSP involves generating schedules to allocate operations to different machines considering only one objective, while MOJSSP considers more than one objective in the scheduling process. SOJSSP and MOJSSP are typical NP-hard optimization problems which have significant values in real production. Intelligent Water Drops (IWD) is a new type of meta-heuristics which shows excellent ability of solving optimization problems. In this research, IWD is improved and customized to solve SOJSSP and MOJSSP problems. Experiments have been conducted, and the results show that the enhanced algorithms can solve these two types of problems better compared with current literature. To the best of the authors’ knowledge, this is among the first research employing IWD for solving SOJSSP and MOJSSP.