A nature inspired intelligent water drops evolutionary algorithm for parallel processor scheduling with rejection |
| |
Affiliation: | 1. Department of Mathematics, Zhejiang Sci-Tech University, Hangzhou 310018, China;2. Department of Computer Science, California State University Los Angeles, Los Angeles, CA 90032, USA;3. Department of Computer Science, The University of Texas at Dallas, Richardson, TX 75080, USA;4. School of Information, Renmin University of China, Beijing 100872, China;1. Computer Science, Faculty of Computers and Informatics, Suez Canal University, Egypt;2. National Authority of Remote Sensing and Space Sciences, Cairo, Egypt;1. Dipartimento di Informatica, Università di Pisa, Italy;2. Dipartimento di Matematica e Informatica, Università di Perugia, Italy |
| |
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 undesirable 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. |
| |
Keywords: | Intelligent water drops Parallel local search Neighborhood structures Order scheduling Rejection |
本文献已被 ScienceDirect 等数据库收录! |
|