An efficient and fast local search based heuristic for reel management in a production line of oil extraction pipes

摘要

The manufacturing of oil extraction pipes involves several steps of pipe processing in a sequence of machines. The pipes are attached to reels that are moved between the machines by cranes. As the physical space and the reach of the cranes are limited, the motion must follow specific paths, which must comply with several movement constraints. A poorly designed reel movement plan will require a long time for reel positioning and can even lead the facility to a deadlock. This work proposes a reel management heuristic that, given the current reel positions, the facility configuration, and the production plan to be executed, builds a full reel movement plan in a few minutes. The proposed tool optimizes five objectives that are combined into a lexicographical function: task compliance; moves to the uncovered part of the facility; tardiness; earliness; and the number of reel movements performed. The optimized movements are generated by a fast local search based heuristic, which employs a distance metric suitable for measuring distances in this study. That distance metric, which is inspired on the Dijkstra's algorithm, measures the effort for moving a reel from a start vertex to a target vertex. The proposed heuristic for movement planning is conceived as a real-time tool, which is re-run on each time a relevant discrepancy between the planning and the actual behavior of the plant appears; for this reason, the proposed system is allowed a maximum of 300 s of processing time for delivering a complete solution. Comparisons with a heuristic based on ILP and with a VNS procedure were performed, showing that the proposed method reaches either the same performance or a better performance in the objectives, consuming a much smaller processing time.