مقایسه الگوریتم های هیوریستیک در محل ذخیره سازی مسئله تخصیص دو وجهی

This paper discusses the newly defined planar storage location assignment problem (PSLAP). We develop a mathematical programming model and GA-based and dynamic PSLAP heuristic algorithms for the solving procedure. Using the testing set, we compare the performance of GA-based and dynamic PSLAP heuristic algorithms. The mathematical programming model is utilized as a comparison criterion. The comparison results demonstrate that the dynamic PSLAP heuristic algorithm performs better than the other solving procedures. In addition, we describe simulation experiments conducted to investigate the effects of stock yard layout and production schedule instability on the operation of the block stock yard.

At a shipyard, efficient management of assembly blocks is important. In the shipbuilding process, the block refers to a basic unit of a ship. At the design stage, a huge ship is divided into divisions, which are further divided into blocks. The block is assembled by welding pieces of steel at the manufacturing shop and goes through several operations at a shipyard, such as outfitting and painting. Last, assembly blocks are welded together to build a ship on the dry dock. Assembly blocks are actually work-in-progress (WIP) inventories in the shipbuilding process, and the size and the weight of the assembly block are large. The dimensions of the assembly block are usually about 15 m (length) by 15 m (width) by 5 m (height), while some blocks are even bigger. The weight of the assembly block is usually in the range of 100–300 tons, and some blocks weigh more than 500 tons. Because of the considerable size and weight, assembly block operations managers pay special attention to transportation and storage. Shipbuilders utilize specially manufactured heavy-lift crawler vehicles to transport large and heavy assembly blocks. The transporter is a 65-wheel, multiple-axle vehicle that has hydraulic jack lifts that allow it to move under a heavy block, jack it up, and move it to another location for delivery. The specially manufactured transporters move one block at a time by lifting the block with a flat support. When storing an assembly block at the stock yard, an empty location should prepare four props (2 m high) before the transporter arrives. The loaded transporter moves into a space between the props, places the assembly block on the four props, and moves out by itself. Conversely, when retrieving an assembly block from the stock yard, the transporter should first determine an access path to the block. If some blocks are on the access path, the transporter should move obstructive blocks to empty spaces to reach the block. Moving such obstructive blocks is unproductive and should be avoided. It is crucial for block stock yard operations to minimize the number of obstructive block moves by properly determining the assembly block storage location. We prefer to call the problem related to assembly block stock yard operations the planar storage location assignment problem (PSLAP). In the field of seaport container terminal operations, similar problems, such as the storage-space-allocation problem and the storage location assignment problem, have been described (Bazzazi et al., 2009, Kozan and Preston, 2006, Preston and Kozan, 2001 and Zhang et al., 2003). The PSLAP and the storage-related problems in seaport container terminals address the same objective of providing temporary storage to inbound and outbound objects (e.g., containers and assembly blocks). However, transportation operations differ significantly, as yard cranes (e.g., rubber-tire gantry cranes and rail-mounted gantry cranes in seaport container terminals) move the containers. Hence, inbound and outbound containers can perform moves in all three directions (i.e., X, Y, and Z direction) in addressing storage-related problems in seaport container terminals. However, the PSLAP strictly limits the inbound and outbound block movements to only the X and/or Y direction (i.e., only planar moves), because no yard cranes are allowed. At a glance, the PSLAP might be misunderstood as a special type of storage-related problem in seaport container terminals, which is more limited with regard to movement, reduced from three dimensions to two dimensions, along with certain rules for moving sequence operations to maintain efficiency. However, because of differences in transportation operations and the different objectives of the PSLAP and storage-related problems in seaport container terminals, the PSLAP problem should be clearly defined and newly formulated. In addition, a solving procedure should be developed. The PSLAP can be formalized as follows. The assembly block stock yard looks like a rectangular-shaped chessboard divided into cells of m × n (i.e., depth × width). Each cell can store only one block. Several blocks cannot be stored in the same cell by placing one block on the top of the other. Hence, the maximum storage capacity of the stock yard is m × n. The main restriction in efficiently conducting block moves at the stock yard is that blocks can be moved only in the X and/or Y direction; the Z directional move is not allowed. Hence, when storing or retrieving a block at the stock yard, if some blocks are on the moving path of the inbound or outbound block, the obstructive blocks should first be replaced to other empty cells in order to provide the inbound or outbound block with a free moving path. Such work, however, is unproductive and should be avoided. In a real situation, the stock yard operates continuously around the clock. For the purpose of research, however, we divide the continuous time horizon into discrete unit periods of time (e.g., days). For each unit period, the stock yard releases the outbound blocks and stores the inbound blocks. The inbound blocks are already scheduled to leave the stock yard. In this situation, the PSLAP involves retrieving the due outbound blocks from the stock yard, reassigning obstructive blocks to other empty cells, and assigning the inbound blocks to empty cells at the stock yard with the objective of minimizing the number of obstructive block moves. The PSLAP can be formulated as a generalized assignment problem (see Appendix A), but that type of problem is an NP-hard problem (Bazzazi et al., 2009 and Preston and Kozan, 2001). The computation complexity increases exponentially with the number of blocks in the schedule. This makes it difficult to solve in a reasonable time with current exact-optimization solution techniques (e.g., Branch and Bound, Tree Searches). This implies that for large-scaled problems in real situations heuristic techniques have to be used. In this paper, we consider two heuristic algorithms: a genetic algorithm (GA)-based PSLAP heuristic algorithm and a dynamic PSLAP heuristic algorithm. We utilize an efficient GA approach because even the simplest GA implementations, as has been reported, produce relatively good results (Preston and Kozan, 2001). In addition, we utilize a mathematical programming model in Appendix A as a comparison criterion to verify the performance of the two heuristic algorithms for moderate-scale problems that the developed mathematical programming model can solve without too much computation. The rest of this paper is organized as follows. We describe the GA-based PSALP heuristic algorithm in Section 2 and explain the dynamic PSLAP heuristic algorithm in Section 3. Section 4 presents computational experiments, and the final section presents our conclusions.

In this paper, we discuss the newly defined planar storage location assignment problem (PSLAP). The contribution of the paper to the storage location assignment problem literature is to clearly define, newly formulate, and develop the solving procedure of the PSLAP. As mentioned in Section 1, the PSLAP might be misunderstood as a special type of storage-related problem in seaport container terminals, which has a reduced dimension of movement, from three dimensions to two dimensions, along with certain rules governing moving sequence operations to support efficiency. However, the PSLAP is quite different from storage-related problems in that both problems utilize different transportation operations and pursue different objectives. First, we formulated the PSLAP using a mathematical programming model, but that was belonged to the NP-hard problems category. Thus, we developed GA-based and dynamic PSLAP heuristic algorithms for large real-life problems. Using a testing set that simulates a real situation, we verified the performance of the proposed mathematical programming model and the GA-based and dynamic PSLAP heuristic algorithms. The mathematical programming model of the PSLAP was utilized as a comparison criterion to verify the performance of GA-based and dynamic PSLAP heuristic algorithms for moderate-scale problems that the mathematical programming model can solve without significant computation. Compared with the mathematical programming model and the GA-based PSLAP heuristic algorithm, the dynamic PSLAP heuristic algorithm showed promising results. By virtue of the dynamic PSLAP heuristic algorithm’s ability to handle dynamic situations, the dynamic PSLAP heuristic algorithm performed better than (or at least equally well to) the other solving procedures. In addition, we conducted simulation experiments using the dynamic PSLAP heuristic algorithm to investigate the effects of stock yard layout and production schedule instability. The outcomes of simulation experiments showed that, with the same storage capacity, a shallower and less wide stock yard layout improves block stock yard operation. In addition, although the workload is higher, a stable block schedule results in better block stock yard operation than an unstable one.