هوش مصنوعی برای برنامه ریزی سیستم های تولید انعطاف پذیر با استفاده از کران پایین ماتریس قابل دسترس

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.

Flexible manufacturing system (FMS) is a system that can produce multiple types of products using shared resources such as robots, multipurpose machines, and etc. Its characteristics are described as discrete events, resource sharing, concurrency, routing flexibility, and lot size variety. As the complexity of manufacturing systems increase, the development of efficient scheduling and planning techniques for FMS became an important issue. Solving a scheduling problem is to determine a sequence of operations in every job so that the makespan is minimized or the utilization of critical machines is maximized while satisfying the manufacturing objectives. But the problem belongs to the class of NP-hard problems for which optimal polynomial algorithms are hard to develop.

In this paper, we first proposed an admissible View the MathML sourceh¯RCR(M) by taking tl into account in all tokens. We then proposed two new heuristic functions hLBR(M) and hMLR(M) that are more efficient than the previous works in terms of the number of states and computation time. We also proved that the two proposed functions are all admissible. In addition, we proved that hMLR(M) is more informed than hLBR(M) and View the MathML sourceh¯RCR(M). To make hLBR(M) and hMLR(M) more efficient, we modified them and proposed two new heuristic functions, View the MathML sourcehLBR′(M) and View the MathML sourcehMLR′(M). We also proved that they are all admissible and View the MathML sourcehMLR′(M) is more informed than View the MathML sourcehLBR′(M) and View the MathML sourceh¯RCR(M) for single lot size. Finally, we experimented several FMS scheduling problems using random problem generator and compared these results with the previous results. We found that hLBR(M) and hMLR(M) are admissible, and View the MathML sourcehLBR′(M) and View the MathML sourcehMLR′(M) are admissible for single lot size. Also, we verified that four newly proposed heuristic functions are more efficient than View the MathML sourceh¯RCR(M) on average, and the experimental results show that they are very promising.