A nature inspired intelligent water drops evolutionary algorithm for parallel processor scheduling with rejection

Abstract

Scheduling has become a popular area for artificial intelligence and expert system researchers during last decade. In this paper, a new metaheuristic algorithm entitled Intelligent Water Drops (IWD) is adapted for solving a generalized kind of order scheduling problem where rejection of received orders is allowed with a penalty cost. At the beginning of production period, a set of orders are received by manufacturer. Due to capacity limit, the manufacturer can only process a subset of orders and has to decide to reject some of un-desirable orders. The accepted orders are proceed to be scheduled by a set of identical parallel processors in shop floor. The objective is to select the best set of orders with high contribution in manufacturer's benefit and then find the appropriate schedule of accepted orders minimizing the number of tardy orders. To effectively solve the suggested problem, the Lexicographic utility function is customized to address different objectives and then an IWD algorithm which is based on the process of the natural rivers and the interactions among water drops in a river, is devised. To further enhance the performance of basic IWD, an Iterated Local Search (ILS) heuristic is also incorporated into the main algorithm. To demonstrate the applicability of suggested problem and also show the effectiveness of enhanced IWD with ILS, a real-world application in commercial printing industry is presented and the performance of algorithm is compared with traditional algorithms like GA, DE and ACO.