Heuristic search for scheduling flexible manufacturing systems using lower bound reachability matrix |
| |
| Affiliation: | 1. Instrumentation and Control Research Group, POSCO Technical Laboratories, 1, Goedong-Dong, Nam-Gu, Pohang, Gyungbuk 790-300, Republic of Korea;2. Division of Electrical and Computer Engineering, Pohang University of Science and Technology, San 31, Hyoja-Dong, Nam-Gu, Pohang, Gyungbuk 790-784, Republic of Korea;1. Federal University of São Carlos – UFSCar, Department of Computer Science – Rod, Washington Luís km 235, CEP 13565-905 São Carlos, SP, Brazil;2. University of São Paulo – USP, Department of Mechanical Engineer, Avenida dos Trabalhadores São-carlense, 400 – Parque Arnold Schimidt, 13566-590 São Carlos, SP, Brazil;1. Department of Engineering Management, Marmara University, 34722 ?stanbul, Turkey;2. Department of Industrial Engineering, Marmara University, 34722 ?stanbul, Turkey;1. State Key Laboratory of Digital Manufacturing Equipment & Technology, School of Mechanical Science and Engineering, Huazhong University of Science and Technology, Wuhan 430074, PR China;2. School of Automobile and Traffic Engineering, Wuhan University of Science and Technology, Wuhan 430081, PR China;3. Environmental and Ecological Engineering, Purdue University, West Lafayette, 47906, USA;1. School of Computer Science and Engineering, Nanjing University of Science and Technology, Nanjing 210094, China;2. Department of Electrical and Computer Engineering, New Jersey Institute of Technology, Newark, NJ 07102, USA;3. Key Laboratory of Embedded System and Service Computing, Ministry of Education, Tongji University, Shanghai 201804, China;1. Key Laboratory of Advanced Process Control for Light Industry (Ministry of Education), Jiangnan Universiy, Wuxi 214122, PR China;2. College of Electrical Engineering, Zhejiang University, Hangzhou 310058, PR China;1. Department of Computing, University of Oviedo, Spain;2. Department of Mathematics, Statistics and Computing, University of Cantabria, Spain |
| |
| Abstract: | For scheduling flexible manufacturing systems efficiently, we propose new heuristic functions for A* algorithm that is based on the T-timed Petri net. In minimizing makespan, the proposed heuristic functions are usually more efficient than the previous functions in the required number of states and computation time. We prove that these heuristic functions are all admissible and one of them is more informed than that using resource cost reachability matrix. We also propose improved versions of these heuristic functions that find a first near-optimal solution faster. In addition, we modify the heuristic function of Yu, Reyes, Cang, and Lloyd (2003b) and propose an admissible version in all states. The experimental results using a random problem generator show that the proposed heuristic functions perform better as we expected. |
| |
| Keywords: | |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
