TY - JOUR
T1 - Modified Dynamic Programming Algorithm for Optimization of Total Energy Consumption in Flexible Manufacturing Systems
AU - Li, Xiaoling
AU - Xing, Keyi
AU - Zhou, Mengchu
AU - Wang, Xinnian
AU - Wu, Yunchao
N1 - Funding Information:
Manuscript received May 31, 2018; accepted June 24, 2018. Date of publication July 19, 2018; date of current version April 5, 2019. This work was supported by the National Natural Science Foundation of China under Grant 61573278. This paper was recommended for publication by Associate Editor F. Chu and Editor J. Li upon evaluation of the reviewers’ comments. (Corresponding author: Keyi Xing.) X. Li, K. Xing, X. Wang, and Y. Wu are with the State Key Laboratory for Manufacturing Systems Engineering, Systems Engineering Institute, Xi’an Jiaotong University, Xi’an 710049, China (e-mail: xl.li90@stu.xjtu.edu.cn; kyxing@mail.xjtu.edu.cn).
Publisher Copyright:
© 2004-2012 IEEE.
PY - 2019/4
Y1 - 2019/4
N2 - Based on the Petri net (PN) models of the flexible manufacturing systems (FMSs), this paper focuses on solving the scheduling problem of minimizing the total energy consumption of FMSs. In the view of different energy consumption rates of resources under different working statuses, two energy consumption functions are considered. The dynamic programming (DP) models of the scheduling problems based on PNs are established, where a reachable marking of a PN model, start processing time vector, route vector, and the transition sequence leading to the reachable marking from the initial one, is regarded as a state, and the Bellman equation is based on transition firing. For small-size scheduling problems, their optimal solutions can be obtained by the presented DP algorithm. However, it is difficult to solve larger-scale ones since the number of explored states increases exponentially with the problem size, which makes DP computationally infeasible. To obtain an optimal or suboptimal schedule in an acceptable time, modified DP (MDP) algorithm is proposed, in which fewer states are explored. In MDP, two ways are introduced through which only the most promising states are explored. One is keeping only one transition sequence for each marking through an evaluation function. Another is selecting the most promising states in each stage for further exploration through a heuristic function. To guarantee that the generated states are safe, a deadlock controller is applied in the recursion procedure of MDP. Experimental results on manufacturing systems and comparisons with existing works are provided to show the effectiveness of MDP. Note to Practitioners - This paper is motivated by the need of optimizing the energy consumption of manufacturing systems, considering the increasing energy cost and environmental concerns. Existing studies on energy optimization rarely focus on flexible manufacturing systems (FMSs) which exhibit a high degree of resource sharing and route flexibility and can be highly adaptable to various production plans and goals. Scheduling becomes more challenging when facing deadlock-prone FMSs. This paper provides a method to solve this complex scheduling problem efficiently. In this paper, dynamic programming (DP) is formulated for it, and the optimal energy consumption schedules are found. Considering the computational burden of implementing DP in the scheduling of large-size FMSs, a novel scheduling method named modified DP (MDP) is proposed. Experimental tests on an FMS and a stamping system suggest that MDP can successfully find feasible solutions. Besides, it can be applied to other FMS scheduling problems and industrial cases, once their processing time of operations and energy consumption of resources per unit time are known.
AB - Based on the Petri net (PN) models of the flexible manufacturing systems (FMSs), this paper focuses on solving the scheduling problem of minimizing the total energy consumption of FMSs. In the view of different energy consumption rates of resources under different working statuses, two energy consumption functions are considered. The dynamic programming (DP) models of the scheduling problems based on PNs are established, where a reachable marking of a PN model, start processing time vector, route vector, and the transition sequence leading to the reachable marking from the initial one, is regarded as a state, and the Bellman equation is based on transition firing. For small-size scheduling problems, their optimal solutions can be obtained by the presented DP algorithm. However, it is difficult to solve larger-scale ones since the number of explored states increases exponentially with the problem size, which makes DP computationally infeasible. To obtain an optimal or suboptimal schedule in an acceptable time, modified DP (MDP) algorithm is proposed, in which fewer states are explored. In MDP, two ways are introduced through which only the most promising states are explored. One is keeping only one transition sequence for each marking through an evaluation function. Another is selecting the most promising states in each stage for further exploration through a heuristic function. To guarantee that the generated states are safe, a deadlock controller is applied in the recursion procedure of MDP. Experimental results on manufacturing systems and comparisons with existing works are provided to show the effectiveness of MDP. Note to Practitioners - This paper is motivated by the need of optimizing the energy consumption of manufacturing systems, considering the increasing energy cost and environmental concerns. Existing studies on energy optimization rarely focus on flexible manufacturing systems (FMSs) which exhibit a high degree of resource sharing and route flexibility and can be highly adaptable to various production plans and goals. Scheduling becomes more challenging when facing deadlock-prone FMSs. This paper provides a method to solve this complex scheduling problem efficiently. In this paper, dynamic programming (DP) is formulated for it, and the optimal energy consumption schedules are found. Considering the computational burden of implementing DP in the scheduling of large-size FMSs, a novel scheduling method named modified DP (MDP) is proposed. Experimental tests on an FMS and a stamping system suggest that MDP can successfully find feasible solutions. Besides, it can be applied to other FMS scheduling problems and industrial cases, once their processing time of operations and energy consumption of resources per unit time are known.
KW - Dynamic programming (DP)
KW - flexible manufacturing systems (FMSs)
KW - reachability graph (RG)
KW - scheduling
KW - total energy consumption
UR - http://www.scopus.com/inward/record.url?scp=85050249797&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85050249797&partnerID=8YFLogxK
U2 - 10.1109/TASE.2018.2852722
DO - 10.1109/TASE.2018.2852722
M3 - Article
AN - SCOPUS:85050249797
SN - 1545-5955
VL - 16
SP - 691
EP - 705
JO - IEEE Transactions on Automation Science and Engineering
JF - IEEE Transactions on Automation Science and Engineering
IS - 2
M1 - 8413154
ER -