A Polynomially Solvable Case for Solving Crane Scheduling Problem in Batch Annealing Process

Abstract:

This paper investigates a special case for scheduling of the multi-crane operations in batch annealing process in an iron and steel enterprise so that the completion time of the last annealed coil (makespan) is minimized. Additional no-delay and no-buffer constraints for taking fully advantage of machines are considered. No-delay constraints for machine unloading means technological requires fixed heating time and cooling time that once the heating (cooling) is completed, the furnace (cooler) must be unloaded immediately without any delay by crane. No-buffer constraints for machine unloading means the time gap between the unloading time of one machine for one job and its start time on the next job is exactly equal to the corresponding transportation time. We prove that this problem can be solved optimally in polynomial time where the starting time and ending time of every possible crane movement are formulated.

• Periodical: Applied Mechanics and Materials (Volumes 543-547)
• Pages: 1555-1558
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.543-547.1555
• Online since: March 2014
• Authors: Xie Xie*, Xiang Yu Kong, Yong Yue Zheng, Yan Ping Li
• Keywords: Batch Annealing Process, Crane Scheduling, Polynomial Algorithm, Strongly NP-Hard

References

[1] J.Y. Liu and Y. Jiang, An efficient optimal solution to the two-hoist no-wait cyclic scheduling problem, Operations Research, 55 (2005), 313-327.

DOI: 10.1287/opre.1040.0167

[2] Y. Jiang and J.Y. Liu, Multihoist cyclic scheduling with fixed processing and transfer times, IEEE Trans. on Automation Science and Engineering 4(3) (2007), 435-450.

DOI: 10.1109/tase.2006.884057

[3] A.P. Catherine, B.H. Leonardo and B. Philippe, A two-stage methodology for short-term batch plant scheduling: discrete-event simulation and generic algorithm, Computers & Chemical Engineering, 22(10) (1998), 1461-1481.

DOI: 10.1016/s0098-1354(98)80033-1

[4] S. Moon and A.N. Hrymak, Scheduling of the batch annealing process--deterministic case, Computers & Chemical Engineering, 23 (1999), 1193-1208.

DOI: 10.1016/s0098-1354(99)00285-9

[5] Q.L. Liu, W. Wang, H.R. Zhan, Z.G. Wang and R.G. Liu, Optimal scheduling method for bell-type batch annealing shop and its application, Control Engineering Practice, 13 (2005), 1315-1325.

DOI: 10.1016/j.conengprac.2004.11.017

[6] X. Xie and L.X. Tang, Crane scheduling in batch annealing process, Proceedings of the IEEE ICAL (2008), 2020-(2025).

[7] L.X. Tang, X. Xie and J.Y. Liu, Scheduling of a single crane in batch annealing process, Computers & Operations Research 36 (2009), 2853-2865.

DOI: 10.1016/j.cor.2008.12.014