Rescheduling of Multi-Scenario and Multi-Objective Dynamic Changes of Ship Group Construction

doi:10.16183/j.cnki.jsjtu.2023.274

Abstract

Abstract:

A multi-scenario and multi-objective dynamic change rescheduling algorithm is proposed to address the production schedule delays and the need for adjustments caused by frequent abnormal conditions, such as material delivery delays and equipment failures in the vertical assembly welding process of shipbuilding teams. First, the objective function is selected based on different production stage and abnormal disturbance, and a mathematical model is then developed, incorporating site constraints, task precedence constraints, and human resource constraints. Next, a site allocation algorithm is introduced, and an improved non-dominated sorting algorithm based on reference points is adopted to solve the problem. A cross-checking mechanism implemented, alongside a task-sequence-based mutation operator, and the multi-chromosome mechanism is integrated with the site allocation algorithm. Afterwards, a method for calculating the chromosome sequence distance in the ship group vertical assembly welding rescheduling is proposed, and the difference between the rescheduling algorithm solution and initial plan is described. An R2 indicator is combined with a Pareto-R2 double standard selection operator, which ensures both diversity and convergence of the algorithm. Finally, comparative experiments are conducted based on engineering cases to validate the effectiveness of the proposed rescheduling algorithm.

Key words: small assembly of ship, reschedule, multi-objective optimization, multi-scenario

CLC Number:

TP391
TH186

ZHANG Aoyuan, HU Xiaofeng, ZHANG Yahui. Rescheduling of Multi-Scenario and Multi-Objective Dynamic Changes of Ship Group Construction[J]. Journal of Shanghai Jiao Tong University, 2025, 59(4): 476-488.

Figures/Tables 11

Fig.1

Tab.1

Fig.2

Fig.3

Tab.2

Tab.3

Fig.4

Fig.5

Tab.4

Tab.5

Fig.6

References 24

[1]	周泽麟, 单小芬, 张红伟, 等. 基于模型轮廓识别注册的船舶小组立装配指导技术[J]. 船舶工程, 2022, 44 (Sup.1): 561-564.
	ZHOU Zelin, SHAN Xiaofen, ZHANG Hongwei, et al. Ship sub-assembly assembling guidance based on model contour recognition register[J]. Ship Engineering, 2022, 44 (Sup.1): 561-564.
[2]	王树烽. 船体曲面分段车间排产与调度优化研究[D]. 哈尔滨: 哈尔滨工程大学, 2018.
	WANG Shufeng. Research on planning and scheduling problems for hull curved block workshop[D]. Harbin: Harbin Engineering University, 2018.
[3]	杨志. 不确定条件下船舶平面分段流水线调度方法研究[D]. 上海: 上海交通大学, 2018.
	YANG Zhi. Research on scheduling methods for panel block assembly line under uncertainties[D]. Shanghai: Shanghai Jiao Tong University, 2018.
[4]	李敬花, 余峰, 樊付见. 基于遗传模拟退火融合算法的船舶分段装配序列优化[J]. 计算机集成制造系统, 2013, 19(1): 39-45.
	LI Jinghua, YU Feng, FAN Fujian. Ship block assembly sequence optimization based on genetic simulated annealing algorithm[J]. Computer Integrated Manufacturing Systems, 2013, 19(1): 39-45.
[5]	KWON B, LEE G M. Spatial scheduling for large assembly blocks in shipbuilding[J]. Computers & Industrial Engineering, 2015, 89: 203-212.
[6]	侯金伟, 胡小锋, 徐昇. 多规则融合的船体小组立部件装焊作业调度算法[J]. 船舶工程, 2020, 42(5): 101-107.
	HOU Jinwei, HU Xiaofeng, XU Sheng. Scheduling algorithm for welding work of hull small assembly with multi-rule fusion[J]. Ship Engineering, 2020, 42(5): 101-107.
[7]	ZHANG B, PAN Q, MENG L, et al. A decomposition-based multi-objective evolutionary algorithm for hybrid flowshop rescheduling problem with consistent sublots[J]. International Journal of Production Research, 2023, 61(3): 1013-1038.
[8]	WANG Z, SHEN L, LI X, et al. An improved multi-objective firefly algorithm for energy-efficient hybrid flowshop rescheduling problem[J]. Journal of Cleaner Production, 2023, 385: 135738.
[9]	ZHANG X, HAN Y, KRÓLCZYK G, et al. Rescheduling of distributed manufacturing system with machine breakdowns[J]. Electronics, 2022, 11(2): 249.
[10]	高丽, 周炳海, 杨学良, 等. 基于多规则资源分配的柔性作业车间调度问题多目标集成优化方法[J]. 上海交通大学学报, 2015, 49(8): 1191-1198.
	GAO Li, ZHOU Binghai, YANG Xueliang, et al. A multi-objective integrated optimization method for FJSP based on multi-rule resource allocation[J]. Journal of Shanghai Jiao Tong University, 2015, 49(8): 1191-1198.
[11]	田启华, 黄佳康, 明文豪, 等. 资源约束下产品开发任务调度的多目标优化[J]. 计算机集成制造系统, 2022, 28(2): 564-573.
	TIAN Qihua, HUANG Jiakang, MING Wenhao, et al. Multi-objective optimization of product development task scheduling under resource constraint[J]. Computer Integrated Manufacturing Systems, 2022, 28(2): 564-573.
[12]	何小妹, 董绍华. 多目标多约束混合流水车间插单重调度问题研究[J]. 工程科学学报, 2019, 41(11): 1450-1457.
	HE Xiaomei, DONG Shaohua. Research on rush order insertion rescheduling problem under hybrid flow shop with multi-objective and multi-constraint[J]. Chinese Journal of Engineering, 2019, 41(11): 1450-1457.
[13]	安晓亭, 张梓琪. 基于改进蚁群优化的多目标资源受限项目调度方法[J]. 系统工程理论与实践, 2019, 39(2): 509-519. doi: 10.12011/1000-6788-2017-0983-11
	AN Xiaoting, ZHANG Ziqi. Multi-objective resource constrained project scheduling problem based on improved ant colony optimization[J]. Systems Engineering Theory Practice, 2019, 39(2): 509-519.
[14]	BAO J, ZHENG X, ZHANG J, et al. Data-driven process planning for shipbuilding[J]. AI EDAM, 2018, 32(1): 122-130.
[15]	张亚辉. 多约束条件下多目标双边装配线再平衡方法研究[D]. 上海: 上海交通大学, 2020.
	ZHANG Yahui. Research on multi-objective two-sided assembly line rebalancing problem with multiple constrains[D]. Shanghai: Shanghai Jiao Tong University, 2020.
[16]	汤洪涛, 王丹南, 邵益平, 等. 基于改进候鸟迁徙优化的多目标批量流混合流水车间调度[J]. 上海交通大学学报, 2022, 56(2): 201-213. doi: 10.16183/j.cnki.jsjtu.2020.435
	TANG Hongtao, WANG Dannan, SHAO Yiping, et al. A modified migrating birds optimization for multi-objective lot streaming hybrid flowshop scheduling[J]. Journal of Shanghai Jiao Tong University, 2022, 56(2): 201-213.
[17]	LIU Y C, LIU J C, LI T J, et al. An R2 indicator and weight vector-based evolutionary algorithm for multi-objective optimization[J]. Soft Computing: A Fusion of Foundations, Methodologies and Applications, 2020, 24(5): 5079-5100.
[18]	ZHANG X, TIAN Y, CHENG R, et al. An efficient approach to non-dominated sorting for evolutionary multi-objective optimization[J]. IEEE Transactions on Evolutionary Computation, 2015, 19(2): 201-213.
[19]	KHAN I H. Assessing different crossover operators for travelling salesman problem[J]. International Journal of Intelligent Systems and Applications, 2015, 7(11): 19-25.
[20]	AGRAWAL R B, DEB K. Simulated binary crossover for continuous search space[J]. Complex Systems, 2000, 9(3): 115-148.
[21]	DEB K, GOYAL M. A combined genetic adaptive search (GeneAS) for engineering design[J]. Computer Science and informatics, 1996, 26: 30-45.
[22]	LOZANO P T. Spatial planning: A configuration space approach[M]. New York, USA: Springer, 1990.
[23]	聂兰顺, 靳金涛, 战德臣, 等. 基于配置空间理论的启发式空间调度算法[J]. 计算机集成制造系统, 2013, 19(10): 2590-2598. doi: 10.13196/j.cims.2013.10.NIELanshun.20131025
	NIE Lanshun, JIN Jintao, ZHAN Dechen, et al. Heuristic spatial scheduling algorithm based on configuration space theory[J]. Computer Integrated Manufacturing Systems, 2013, 19(10): 2590-2598.
[24]	FONSECA C M, PAQUETE L, LOPEZ-IBANEZ M. An improved dimension-sweep algorithm for the hypervolume indicator[C]// International Conference on Evolutionary Computation. Vancouver, Canada: IEEE, 2006: 1157-1163.

目标函数	前期			中期			后期
目标函数	异常1	异常2	异常3	异常1	异常2	异常3	异常1	异常2	异常3
最小化最大完工时间	√	√	√	√			√
最小化开工时间偏差	√			√	√	√	√
最大化空间利用率	√	√	√
最大化工人利用率	√	√	√		√			√
最小化延期时间						√	√	√	√
最大化紧急任务如期交付			√			√			√

形状编号	形状	顶点坐标集
1	直角三角形	{(0, 0), (5, 0), (0, 3)}
2	正方形	{(0, 0, )(3, 0)(3, 3), (0, 3)}
3	直角梯形	{(0, 0), (5, 0), (3, 3)(0, 3)}
4	等腰梯形	{(0, 0), (5, 0), (3.9, 3), (1.1, 3)}
5	五边形	{(0, 0), (5, 0), (3.9, 3), (1.1, 3) (0, 1.5)}
6	四边形	{(0, 0), (3.0), (3.4, 1), (0, 3)}
7	一般三角形	{(0, 0), (5, 0), (4.2, 3)}
8	矩形1	{(0, 0), (14, 0), (14, 3), (0, 3)}
9	矩形2	{(0, 0), (14, 0), (14, 5), (0, 5)}
10	平行四边形1	{(0, 0), (12.3, 0), (14, 3), (1.7, 3)}
11	平行四边形2	{(0, 0), (13.1, 0), (14, 5), (0.9, 5)}
12	六边形	{(0, 0), (10.5, 0), (14, 2), (14, 5), (3.5, 5), (0, 3)}
13	横躺等腰梯形	{(0, 0), (14.4, 0), (15, 3), (1.4, 7.9)}
14	不规则五边形	{(0, 0), (14.4, 0), (15, 3), (9.6, 4.9), (0.9, 4.9)}

部件类型	部件编号	部件形状
肋板	1, 2, 3, 4, 5, 6, 7	五边形
	8, 9, 10, 11, 12, 13, 14	等腰梯形
	15, 16, 17, 18	直角梯形
	19, 20, 21, 22	直角三角形
纵桁	23	横躺等腰梯形
	24	不规则五边形
	25	六边形
	26	平行四边形2
小组部件	27	横躺等腰梯形
	28	不规则五边形
	29	六边形
	30	平行四边形2

算法	最大完工时间	开工时间偏差	空间利用率	工人利用率
改进前的NSGA-III	94	398	0.41	0.65
	97	287	0.39	0.58
	99	490	0.43	0.59
	94	398	0.41	0.65
本文算法	93	256	0.43	0.68

算法	开工时间偏差	工人利用率	延期时间	紧急任务提前交付
改进前的NSGA-III	39	0.60	95	5
	63	0.63	93	9
	72	0.62	92	6
	65	0.56	94	11
	56	0.55	96	11
	69	0.56	97	11
本文算法	57	0.65	91	11