船舶专业外文文献之欧阳物创编Word格式文档下载.docx

1、时间：2021.02.07命题人：欧阳物Abstract: This paper addresses the spatial scheduling problem （SPP） for large assembly blocks, which arises in a shipyard assembly shop. The spatial scheduling problem is to schedule a set of jobs, of which each requires its physical space in a restricted space. This problem is c

2、omplicated because both the scheduling of assemblies with different due dates and earliest starting times and the spatial allocation of blocks with different sizes and loads must be considered simultaneously. This problem under consideration aims to the minimization of both the makespan and the load

3、 balance and includes various real-world constraints, which includes the possible directional rotation of blocks, the existence of symmetric blocks, and the assignment of some blocks to designated workplaces or work teams. The problem is formulated as a mixed integer programming （MIP） model and solv

4、ed by a commercially available solver. A two-stage heuristic algorithm has been developed to use dispatching priority rules and a diagonal fill space allocation method, which is a modification of bottom-left-fill space allocation method. The comparison and computational results shows the proposed MI

5、P model accommodates various constraints and the proposed heuristic algorithm solves the spatial scheduling problems effectively and efficiently.Keywords:Large assembly block; Spatial scheduling; Load balancing; Makespan; Shipbuilding1. IntroductionShipbuilding is a complex production process charac

6、terized by heavy and large parts, various equipment, skilled professionals, prolonged lead time, and heterogeneous resource requirements. The shipbuilding process is divided into sub processes in the shipyard, including ship design, cutting and bending operations, block assembly, outfitting, paintin

7、g, pre-erection and erection. The assembly blocks are called the minor assembly block, the sub assembly block, and the large assembly block according to their size and progresses in the course of assembly processes. This paper focuses on the spatial scheduling problem of large assembly blocks in ass

8、embly shops. Fig. 1 shows a snapshot of large assembly blocks in a shipyard assembly shop.Recently, the researchers and practitioners at academia and shipbuilding industries recently got together at “Smart Production Technology Forum in Shipbuilding and Ocean Plant Industries” to recognize that ther

9、e are various spatial scheduling problems in every aspect of shipbuilding due to the limited space, facilities, equipment, labor and time. The SPPs occur in various working areas such as cutting and blast shops, assembly shops, outfitting shops, pre-erection yard, and dry docks. The SPP at different

10、 areas has different requirements and constraints to characterize the unique SPPs. In addition, the depletion of energy resources on land put more emphasis on the ocean development. The shipbuilding industries face the transition of focus from the traditional shipbuilding to ocean plant manufacturin

11、g. Therefore, the diversity of assembly blocks, materials, facilities and operations in ship yards increases rapidly.There are some solution providers such as Siemens and Dassult Systems to provide integrated software including product life management, enterprise resource planning system, simulation

12、 and etc. They indicated the needs of efficient algorithms to solve medium- to large-sized SPP problems in 20min, so that the shop can quickly re-optimize the production plan upon the frequent and unexpected changes in shop floors with the ongoing operations on exiting blocks intact.There are many d

13、ifferent applications which require efficient scheduling algorithms with various constraints and characteristics （Kim and Moon, 2003, Kim et al., 2013, Nguyen and Yun, 2014andYan et al., 2014）. However, the spatial scheduling problem which considers spatial layout and dynamic job scheduling has not

14、been studied extensively. Until now, spatial scheduling has to be carried out by human schedulers only with their experiences and historical data. Even when human experts have much experience in spatial scheduling, it takes a long time and intensive effort to produce a satisfactory schedule, due to

15、the complexity of considering blocks geometric shapes, loads, required facilities, etc. In practice, spatial scheduling for more than a six-month period is beyond the human schedulers capacity. Moreover, the space in the working areas tends to be the most critical resource in shipbuilding. Therefore

16、, the effective management of spatial resources through automation of the spatial scheduling process is a critical issue in the improvement of productivity in shipbuilding plants.A shipyard assembly shop is consisted of pinned workplaces, equipment, and overhang cranes. Due to the heavy weight of la

17、rge assembly block, overhang cranes are used to access any areas over other objects without any hindrance in the assembly shop. The height of cranes can limit the height of blocks that can be assembled in the shop. The shop can be considered as a two-dimensional space. The blocks are placed on preci

18、sely pinned workplaces.Once the block is allocated to a certain area in a workplace, it is desirable not to move the block again to different locations due to the size and weight of the large assembly blocks. Therefore, it is important to allocate the workspace to each block carefully, so that the w

19、orkspace in an assembly shop can be utilized in a most efficient way. In addition, since each block has its due date which is pre-determined at the stage of ship design, the tardiness of a block assembly can lead to severe delay in the following operations. Therefore, in the spatial scheduling probl

20、em for large assembly blocks, the scheduling of assembly processes for blocks and the allocation of blocks to specific locations in workplaces must be considered at the same time. As the terminology suggests, spatial scheduling pursues the optimal spatial layout and the dynamic schedule which can al

21、so satisfy traditional scheduling constraints simultaneously. In addition, there are many constraints or requirements which are serious concerns on shop floors and these complicate the SPP. The constraints or requirements this study considered are explained here: （1） Blocks can be put in either dire

22、ctions, horizontal or vertical. （2） Since the ship is symmetric around the centerline, there exist symmetric blocks. These symmetric blocks are required to be put next to each other on the same workplace. （3） Some blocks are required to be put on a certain special area of the workplace, because the

23、work teams on that area has special equipment or skills to achieve a certain level of quality or complete the necessary tasks. （4） Frequently, the production plan may not be implemented as planned, so that frequent modifications in production plans are required to cope with the changes in the shop.

24、At these modifications, it is required to produce a new modified production plan which does not remove or move the pre-existing blocks in the workplace to complete the ongoing operations. （5） If possible at any time, the load balancing over the work teams, i.e., workplaces are desirable in order to

25、keep all task assignments to work teams fair and uniform.Lee, Lee, and Choi （1996） studied a spatial scheduling that considers not only traditional scheduling constraints like resource capacity and due dates, but also dynamic spatial layout of the objects. They used two-dimensional arrangement algor

26、ithm developed by Lozano-Perez （1983） to determine the spatial layout of blocks in shipbuilding. Koh, Park, Choi, and Joo （1999） developed a block assembly scheduling system for a shipbuilding company. They proposed a two-phase approach that includes a scheduling phase and a spatial layout phase. Ko

27、h, Eom, and Jang （2008） extended their precious works （Koh et al., 1999） by proposing the largest contact area policy to select a better allocation of blocks. Cho, Chung, Park, Park, and Kim （2001） proposed a spatial scheduling system for block painting process in shipbuilding, including block sched

28、uling, four arrangement algorithms and block assignment algorithm. Park et al. （2002） extended Cho et al. （2001） utilizing strategy simulation in two consecutive operations of blasting and painting. Shin, Kwon, and Ryu （2008） proposed a bottom-left-fill heuristic method for spatial planning of block

29、 assemblies and suggested a placement algorithm for blocks by differential evolution arrangement algorithm. Liu, Chua, and Wee （2011） proposed a simulation model which enabled multiple priority rules to be compared. Zheng, Jiang, and Chen （2012） proposed a mathematical programming model for spatial

30、scheduling and used several heuristic spatial scheduling strategies （grid searching and genetic algorithm）. Zhang and Chen （2012） proposed another mathematical programming model and proposed the agglomeration algorithm.This study presents a novel mixed integer programming （MIP） formulation to consid

31、er block rotations, symmetrical blocks, pre-existing blocks, load balancing and allocation of certain blocks to pre-determined workspace. The proposed MIP models were implemented by commercially available software, LINGO and problems of various sizes are tested. The computational results show that t

32、he MIP model is extremely difficult to solve as the size of problems grows. To efficiently solve the problem, a two-stage heuristic algorithm has been proposed.Section 2 describes spatial scheduling problems and assumptions which are used in this study. Section 3 presents a mixed integer programming formulation. In Section 4, a two-stage heuristic algorithm has been proposed, including block dispatching priority rules and a diagonal fill space allocation heuristic method, which is modified from the bottom-left-fill space allocation method. Computational results are provided in