Problem Specific Variable Selection Rules for Constraint Programming: A Type II Mixed Model Assembly Line Balancing Problem Case

Figures & data

Figure 1. a) Multi model assembly line b) mixed model assembly line.

Figure 2. The problem place in the ALBPs literature.

Table 1. Experimental sets.

	# Model	# Task	# Station
Heskiaoff	2	28	8
Heskiaoff	3	28	8
Sawyer	2	30	8
Sawyer	3	30	8
Kilbridge	2	45	12
Kilbridge	3	45	12
Tongue	2	70	20
Tongue	3	70	20
WeeMag	2	75	20
WeeMag	4	75	20
Scholl	2	297	45
Scholl	4	297	45

Table 2. TTBR rules solution results.

	MP		Standard CP		TTBR I		TTBR II		TTBR III
	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time
Heskiaoff 2	488	610	490	42	488	43	488	128	488	452
Heskiaoff 3	664	2	665	180	664	11	664	18	664	8
Sawyer 2	367	0.7	367	7	367	0.35	367	0.4	367	0.2
Sawyer 3	658	2.5	658	17	658	0.45	658	0.8	658	0.4
Kilbridge 2	375	460	376	1040	375	11	375	3	375	98
Kilbridge 3	597	240	602	123	597	3590	598	61	598	96
Tongue 2	403	1460	400	2980	397	25	399	13	398	68
Tongue 3	615	100	612	524	603	190	600	105	604	265
WeeMag 2	154	235	159	28	156	5	155	53	155	437
WeeMag 4	311	290	322	2240	312	304	311	186	311	488
Scholl 2	4242	3550	3199	2918	3170	1438	3165	366	3162	1616
Scholl 4	8021	2150	6495	2659	6396	1551	6388	1300	6393	777
	MP		Standard CP		TTBR IV		TTBR V		TTBR VI
	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time
Heskiaoff 2	488	610	490	42	489	72	488	472	489	230
Heskiaoff 3	664	2	665	180	665	775	664	9	664	129
Sawyer 2	367	0.7	367	7	367	3.2	367	0.15	367	3
Sawyer 3	658	2.5	658	17	658	2.5	658	0.3	658	2.5
Kilbridge 2	375	460	376	1040	376	325	375	64	376	120
Kilbridge 3	597	240	602	123	600	555	598	90	602	245
Tongue 2	403	1460	400	2980	406	10	400	26	405	118
Tongue 3	615	100	612	524	608	222	604	248	608	222
WeeMag 2	154	235	159	28	158	271	156	10	158	17
WeeMag 4	311	290	322	2240	315	28	310	197	315	350
Scholl 2	4242	3550	3199	2918	3198	323	3168	1700	3199	182
Scholl 4	8021	2150	6495	2659	6447	1702	6401	1086	6450	600

Table 3. PRBR rules solution results.

	MP		Standard CP		PRBR I		PRBR II		PRBR III		PRBR IV
	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time
Heskiaoff 2	488	610	490	42	489	224	488	508	489	41	489	27
Heskiaoff 3	664	2	665	180	664	32	664	240	664	130	664	158
Sawyer 2	367	0.7	367	7	367	1.3	367	0.95	367	0.3	367	1.6
Sawyer 3	658	2.5	658	17	658	1.7	658	2.5	658	3	658	8
Kilbridge 2	375	460	376	1040	376	180	376	115	376	8	376	105
Kilbridge 3	597	240	602	123	599	440	599	523	600	170	599	123
Tongue 2	403	1460	400	2980	400	27	404	65	406	557	401	555
Tongue 3	615	100	612	524	603	425	610	105	609	87	606	38
WeeMag 2	154	235	159	28	158	356	158	343	156	42	160	33
WeeMag 4	311	290	322	2240	314	376	314	310	312	285	312	172
Scholl 2	4242	3550	3199	2918	3277	931	3260	332	3254	1073	3286	2504
Scholl 4	8021	2150	6495	2659	6651	563	6516	1592	6487	687	6658	1146
	MP		Standard CP		PRBR V		PRBR VI		PRBR VII		PRBR VIII
	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time
Heskiaoff 2	488	610	490	42	489	63	489	4	489	9	489	88
Heskiaoff 3	664	2	665	180	664	10	664	44	664	61	664	367
Sawyer 2	367	0.7	367	7	367	0.6	367	0.6	367	0.5	367	0.5
Sawyer 3	658	2.5	658	17	658	3	658	2.5	658	0.4	658	1
Kilbridge 2	375	460	376	1040	376	50	377	13	375	180	377	25
Kilbridge 3	597	240	602	123	600	546	599	100	599	70	601	170
Tongue 2	403	1460	400	2980	405	210	400	175	404	25	404	58
Tongue 3	615	100	612	524	609	50	603	125	604	230	608	225
WeeMag 2	154	235	159	28	158	27	159	428	156	54	158	72
WeeMag 4	311	290	322	2240	313	482	316	194	313	313	314	174
Scholl 2	4242	3550	3199	2918	3199	1237	3289	511	3201	1056	3258	386
Scholl 4	8021	2150	6495	2659	6507	1200	6646	1453	6409	980	6639	1035

Table 4. PR_TTBR rules solution results.

	MP		Standard CP		PR_TTBR I		PR_TTBR II		PR_TTBR III		PR_TTBR IV
	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time
Heskiaoff 2	488	610	490	42	489	16	489	9	488	505	489	7
Heskiaoff 3	664	2	665	180	664	1	664	27	664	53	664	51
Sawyer 2	367	0.7	367	7	367	1.69	367	0.53	367	0.38	367	0.36
Sawyer 3	658	2.5	658	17	658	9	658	7	658	25	658	5
Kilbridge 2	375	460	376	1040	376	568	376	180	375	528	375	65
Kilbridge 3	597	240	602	123	599	350	599	105	599	358	599	17
Tongue 2	403	1460	400	2980	400	145	400	139	404	7	400	565
Tongue 3	615	100	612	524	601	380	600	325	609	73	607	529
WeeMag 2	154	235	159	28	156	219	157	476	156	103	156	32
WeeMag 4	311	290	322	2240	313	544	314	62	312	323	311	433
Scholl 2	4242	3550	3199	2918	3304	1307	3282	200	3276	210	3242	725
Scholl 4	8021	2150	6495	2659	6642	477	6636	1264	6535	893	6487	1089

Table 5. CP rules solution results.

	MP		Standard CP		CP I		CP II
	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time	Best Solution	CPU time
Heskiaoff 2	488	610	490	42	489	189	488	362
Heskiaoff 3	664	2	665	180	664	324	664	56
Sawyer 2	367	0,7	367	7	367	8,5	367	0,5
Sawyer 3	658	2,5	658	17	658	3,5	658	1,2
Kilbridge 2	375	460	376	1040	376	120	375	89
Kilbridge 3	597	240	602	123	601	340	598	220
Tongue 2	403	1460	400	2980	404	335	400	15
Tongue 3	615	100	612	524	612	61	601	85
WeeMag 2	154	235	159	28	157	74	156	18
WeeMag 4	311	290	322	2240	317	358	312	379
Scholl 2	4242	3550	3199	918	3278	1556	3175	1451
Scholl 4	8021	2150	6495	2659	6470	1634	6418	1082