Modeling and optimization of cyclic hoist schedules in an electroplating line

Abstract

This paper deals with the modeling, analysis and optimization of a specific kind of real industrial problems. This class of problems is known in the literature as Cyclic Hoist Scheduling Problem (CHSP). In such class of problems, several jobs have to flow through a production line according to an ordered bath sequence. The CHSPs appear in the manufacturing facilities to achieve a mass production and to search a repetitive sequence of moves for the hoist. In this paper, we develop P-Temporal Petri Net models to represent the behavior and validate certain qualitative properties of the basic production line. Afterward, complex configurations of the production line are modeled and their properties such as reachability of desired functioning (cyclic operation), deadlock-free, resource sharing and management are checked and validated. A mathematical analysis and a simulation study of all proposed Petri net models are carried out using mathematical fundaments of Petri nets and a Visual Object Net ++ tool. The second part of the paper deals with the development of a mixed integer linear programming models to optimize processing of each line configuration. Optimal manufacturing plans of the studied system with cyclic processing sequences are defined and the feasibility of optimal cyclic scheduling of each configuration is proved.

Keywords

Manufacturing lines / processing tanks / cyclic scheduling / Petri nets / mixed integer linear programming / modeling / optimization

References

[1] Armstrong R., Lei L., Gu S.. A bounding scheme for deriving the minimal cycle time of a single-transporter N-stage process with time-window constraints. European Journal of Operational Research, 1994, 75: 1-11.

[2] Baptiste P., Legeard B., Varnier C.. Hoist scheduling problem: an approach based on Constraint Logic Programming. IEEE International Conference on Robotics and Automation, 1992

[3] Collart Dutilleul S., Denat J.-P.. P-time Petri nets and the Hoist Scheduling Problem. International Conference on Systems, Man, and Cybernetics, 1998

[4] Drath R.. Available on onlie, 1997

[5] El-Amraoui Combinatorial optimization approaches for multi-part cyclic hoist scheduling problem. 4OR, 2015, 13(1): 111-112.

[6] El Amraoui A., Manier M.-A., El Moudni A., Benrejeb M.. A linear optimization approach to the heterogeneous r-cyclic hoist scheduling problem. Computers & Industrial Engineering, 2013, 65(3): 360-369.

[7] El Amraoui A., Manier M.-A., El Moudni A., Benrejeb M.. A genetic algorithm approach for a single Hoist Scheduling Problem with time window constraints. Engineering Applications of Artificial Intelligence, 2013, 26(7): 1761-1771.

[8] El Amraoui A., Manier M.-A., El Moudni A., Benrejeb M.. Resolution of the multi-part cyclic hoist scheduling problem with bounded processing times in complex lines’ configuration. European Journal of Industrial Engineering, 2012, 6(4): 454-473.

[9] El Amraoui A., Nait-Sidi-Moh A.. P-Temporal Petri Nets for Hoist Scheduling Problem. 14th IFAC Symposium on Information Control Problems in Manufacturing Bucharest, 2012

[10] Fleury G., Gourgand M., Lacomme P.. Metaheuristics for the Stochastic Hoist Scheduling Problem (SHSP). International Journal of Production Research, 2001, 39(15): 3419-3457.

[11] Hu H., Zhou M.-C.. A Petri net-based discrete-event control of automated manufacturing systems with assembly operations. IEEE Transactions on Control Systems Technology, 2015, 23(2): 513-524.

[12] Ji P., Wan Y. F.. Planning for printed circuit board assembly: the state-of-the-art review. International Journal of Computer Applications in Technology, 2001, 14(4/5/6): 136-144.

[13] Kim J.-H., Lee T.-E.. Schedulability analysis of time-constrained cluster tools with bounded time variation by an extended Petri net. IEEE Transaction on Automation Science and Engineering, 2008, 5(3): 490-503.

[14] Lei L., Wang T.J.. A proof: the cyclic Hoist Scheduling Problem is NP-complete. Dissertation, 1989

[15] Lim J. M.. A genetic algorithm for a single hoist scheduling in the printed-circuit-board electroplating line. Computer and Industrial Engineering, 1997, 33: 789-792.

[16] Liu J., Jiang Y., Zhou Z.. Cyclic scheduling of a single hoist in extended electroplating lines: a comprehensive integer programming solution. IIE Transaction, 2002, 34: 905-914.

[17] Manier M.-A., Bloch C.. A classification for Hoist Scheduling Problem. International Journal of Flexible Manufacturing Systems, 2003, 15: 37-55.

[18] Murata T.. Petri nets: properties, analysis and applications. Proceedings of the IEEE, 1989, 77(4): 541-580.

[19] Nait-Sidi-Moh A., Bakhouya M., Ait-Cheik-Bihi W., Gaber J.. Modeling and performance evaluation of a contract-based electronic signature process. Journal of Universal Computer Science, 2012, 18(5): 676-703.

[20] Nait-Sidi-Moh A.. Contribution à la modélisation, à l'analyse et à la commande des systèmes de transport public par les réseaux de Petri et l'algèbre (Max, Plus). Dissertation, 2003

[21] Paul H. J., Bierwirth C., Kopfer H.. A heuristic procedure for multi-item hoist production line. International Journal of Production Economics, 2007, 105: 54-69.

[22] Phillips L.W., Unger P.S.. Mathematical programming solution of a Hoist Scheduling Program. IIE Transactions, 1976, 8: 219-225.

[23] Shapiro G.W., Nuttle H.L.W.. Hoist Scheduling for a PCB electroplating facility. IIE Transactions, 1988, 20(2): 157-167.

[24] Song W., Zabinsky Z. B., Storch R. L.. An algorithm for scheduling a chemical processing tank line. Production Planning and Control, 1993, 4(4): 323-332.

[25] Subaï C., Baptiste P., Niel E.. Scheduling issues for environmentally responsible manufacturing: the case of hoist scheduling in an electroplating line. International Journal of Production Economics, 2006, 99(1-2): 74-87.

[26] Trouillet B., Korbaa O., Gentina J.C.. Formal approach of FMS cyclic scheduling. IEEE Transactions on Systems, Man, and Cybernetics. Part C: Applications and Reviews, 2007, 37(1): 126-137.

[27] Wu N., Chu C., Zhou M. C.. A Petri net method for schedulability and scheduling problems in single-arm cluster tools with wafer residency time constraints. IEEE Transactions on Semiconductor Manufacturing, 2008, 21(2): 224-237.

[28] Yih Y.. An algorithm for hoist scheduling problems. International Journal of Production Research, 1994, 32(3): 501-16.