Balancing of Cost-Oriented U-Type General Resource-Constrained Assembly Line: New Constraint Programming Models

doi:10.21203/rs.3.rs-844843/v1

In simple assembly line balancing problems, it is assumed that the resources required to perform the tasks are available at the relevant station for task assignment. However, each task may need different resource types depending on the difficulty, complexity and technical requirements of the tasks in real life. For this reason, tasks and resources belonging to these tasks must be assigned to the relevant station while balancing the line. In this study, the resource-constrained U-shaped assembly line balancing problem(U-GRCALBP) is discussed. According to the literature research, there is no study dealing with U-GRCALBP. Two different constraint programming (CP) models that define the resource constraints as "and/or" constraint types with concurrent resource types have been developed. In these models, the sum of resource usage costs and station opening cost minimization is aimed. The models are explained with an illustrative example and the efficiency of the models was tested by deriving new resource constraints on sample data sets. The number of stations obtained, the total number of resources used, total station opening and resource usage costs, and CPU time were used as performance criteria. According to the numerical results, it has been shown that both models are effective in solving the problem.

Assembly line balancing

U-type

general resource constraints

conjunctive constraints

constraint programming

Table 1. The studies about RCALBP in the literature

Studies

Line shape

Resource type

Objective function

Resource constraint type

Solution method

Straight

U-shape

Two-sided

Simple case

General case

Ns

Nr

Ec

E

Tw

Rc

C

Tc

Dedicated

Alternative

Concurrent

Ağpak and Gökçen (2005)

●

MP

Kao et al. (2010)

●

SRA

Kao et al. (2011)

●

RPWBH

Corominas et al. (2011)

●

MP

Chen et al. (2012)

●

GA

Mete and Agpak (2013)

●

MP

Ogan and Azizoglu (2015)

●

MP & BB

Jusop and Ab Rashid (2017)

●

GA

Quyen et al.(2017)

●

GA

Kamarudin and Ab. Rashid (2017)

●

GA

Chen et al.(2018)

●

GA

Pereira (2018)

●

MP

Khalib et al. (2019)

●

GA

Alakas et al. (2020)

●

CP

Alakaş (2021)

●

CP

This study

✓

CP

Ns: number of stations, Nr: number of resources, Ec: Total equipment cost, E: Efficiency, Tw: Total workforce, Rc: Resource cost, C: Cycle time, Tc: Total cost

CP: Constraint Programming, GA: Genetic Algorithm, MP: Mathematical Programming, SRA: Shortest Route Algorithm, RPWBH: Rank Positional Weight Based Heuristic, BB: Branch and Bound

Table 2. The studies about CP and ALBP in the literature

Studies

Line shape

Model type

Objective function

Additional characteristics

Straight

U-shape

Two-sided

Single

Mixed

Ns

C

Tw

Nr

Ms

Tc

Bockmayr and Pisaruk (2001)

●

Combining integer programming method

Del Valle et al. (2003)

●

Pastor et al.(2007)

●

Topaloglu et al. (2012)

●

Rule-based modeling

Alağaş et al. (2013)

●

Stochastic task time

Pınarbaşı et al. (2016)

●

Stochastic task time

Öztürk et al. (2013)

●

Flexible assembly line

Öztürk et al. (2015)

●

Parallel assembly line

Alağaş et al. (2016)

●

Bukchin and Raviv (2018)

●

Equipment selection problem

Pinarbasi et al., 2019)

●

Assignment restrictions

Alakas et al.(2020)

●

Resource constraints

Pınarbaşı and Alakaş (2020)

●

Stochastic task time

Alakas and Toklu (2020)

●

Variable selection rules

Çil and Kizilay (2020)

●

Multi-manned assembly line

Kizilay and Çil (2020)

●

Multi-operator stations

Alakaş (2021)

●

Resource constraints

Pınarbaşı (2021a)

●

Assignment restrictions

Pınarbaşı (2021b)

●

Stochastic task time

This study

✓

Resource constraints

Ns: number of stations, C: Cycle time, Tw: Total workers, Nr: number of resources, Ms: Makespan, Tc: Total station opening and resource usage costs

Table 3 is available in the Supplemental Files section.

Table 4. Data of the illustrative example

Task	Precedence	Task time	Resources
1	-	2	(2A V B) ᴧ (2A V C)
2	-	3	(A V B) ᴧ (A V C)
3	-	2	5A ᴧ (2B V 4C)
4	1	3	(A V 5B) ᴧ (A V C)
5	2	1	(A V 5C) ᴧ (B V 5C)
6	3	1	(4A V 4B) ᴧ 5C
7	4,5	3	(3A V 3B) ᴧ (3A V 5C)
8	5	3	(5A V 4C) ᴧ (5B V 4C)
9	5,6	2	(A V 3B) ᴧ (A V 3C)
10	7,8	2	(A V 4C) ᴧ (5B V 4C)
11	9	2	(5A V 2B) ᴧ 3C
12	11	1	(4A V 4B) ᴧ 4C

Table 5. The illustrative example solution results.

CP-1				CP-2
Station	Assigned Tasks	Station time	Resource type (#)	Station	Assigned Tasks	Station time	Resource type (#)
1	2, 3	5	A(5), B(2)	1	2, 3	5	A(5), B(2)
2	10, 11, 12	5	B(4), C(4)	2	10, 11, 12	5	B(4), C(4)
3	1, 4	5	A(2)	3	1, 4	5	A(2)
4	5, 6, 8	5	B(4) C(5)	4	5, 6, 8	5	B(4) C(5)
5	7, 9	5	A(3)	5	7, 9	5	A(3)

Table 6. Two resources case experiments’ results.

Problem set	# Tasks	Cycle time	CP-1			CP-2
Problem set	# Tasks	Cycle time	# Stations	# Used resources	Total Cost	# Stations	# Used resources	Total Cost
Mitchell	21	14	8	43	516	8	43	516
		18	6	34	404	6	34	404
		25	5	29	346	5	29	346
		35	3	23	262	3	23	262
Heskiaoff	28	110	10	45	540	10	45	540
		138	8	38	448	8	38	448
		205	6	30	348	6	30	348
		324	4	23	256	4	23	256
Sawyer	30	25	14	68	784	15	67	790
		31	12	55	652	12	56	656
		37	10	46	544	11	46	554
		47	8	41	472	8	41	472
Kilbridge	45	55	11	56	658	11	56	658
		69	9	48	558	9	48	558
		92	7	39	446	7	39	446
		110	6	35	400	6	34	400
Tonge	70	196	19	97	1114	22	95	1128
		294	13	72	826	13	71	814
		391	10	58	656	10	58	656
		502	8	49	556	9	48	550

Table 7. Four resources case experiments’ results.

Problem set	# Tasks	Cycle time	CP-1			CP-2
Problem set	# Tasks	Cycle time	# Stations	# Used resources	Total Cost	# Stations	# Used resources	Total Cost
Mitchell	21	14	8	36	392	8	38	404
		18	6	33	334	6	33	334
		25	5	30	302	5	30	306
		35	3	22	224	3	22	224
Heskiaoff	28	110	11	41	462	11	41	462
		138	9	38	394	8	38	392
		205	6	31	314	6	31	314
		324	4	26	246	4	26	246
Sawyer	30	25	18	71	714	15	76	724
		31	12	58	546	11	56	552
		37	10	50	488	10	49	492
		47	8	41	404	8	43	406
Kilbridge	45	55	11	60	624	11	66	642
		69	8	76	674	9	74	676
		92	7	47	452	7	47	454
		110	8	43	420	8	43	418
Tonge	70	196	19	108	1088	19	107	1082
		294	13	78	788	13	84	824
		391	10	66	652	10	67	650
		502	8	60	580	8	57	574

Table 8. Summary results based on the performance measurements.

# Resource type	Model	Min # stations	Min # resources	Min total cost
2	CP-1	4	-	4
	CP-2	-	5	2
4	CP-1	1	6	10
	CP-2	3	4	5

Table 9. CPU time comparison of the proposed models

# Resource type	Model	Mean	Max	Min	Std. Dev.
2	CP-1	3183.90	3600	120.52	1080.20
	CP-2	3330.42	3600	83.02	871.49
4	CP-1	3600	3600	3600	0
	CP-2	3600	3600	3600	0

Table 10. Comparison of results by number of stations

Problem set	# Tasks	Cycle time	Theoretical # Station	Two Resources				Four Resources
Problem set	# Tasks	Cycle time	Theoretical # Station	CP-1	%gap	CP-2	%gap	CP-1	%gap	CP-2	%gap
Mitchell	21	14	8	8	0.00	8	0.00	8	0.00	8	0.00
		18	6	6	0.00	6	0.00	6	0.00	6	0.00
		25	5	5	0.00	5	0.00	5	0.00	5	0.00
		35	3	3	0.00	3	0.00	3	0.00	3	0.00
Heskiaoff	28	110	10	10	0.00	10	0.00	11	9.09	11	9.09
		138	8	8	0.00	8	0.00	9	11.11	8	0.00
		205	5	6	16.67	6	16.67	6	16.67	6	16.67
		324	4	4	0.00	4	0.00	4	0.00	4	0.00
Sawyer	30	25	13	14	7.14	15	13.33	18	27.78	15	13.33
		31	11	12	8.33	12	8.33	12	8.33	11	0.00
		37	9	10	10.00	11	18.18	10	10.00	10	10.00
		47	7	8	12.50	8	12.50	8	12.50	8	12.50
Kilbridge	45	55	10	11	9.09	11	9.09	11	9.09	11	9.09
		69	8	9	11.11	9	11.11	8	0.00	9	11.11
		92	6	7	14.29	7	14.29	7	14.29	7	14.29
		110	5	6	16.67	6	16.67	8	37.50	8	37.50
Tonge	70	196	18	19	5.26	22	18.18	19	5.26	19	5.26
		294	12	13	7.69	13	7.69	13	7.69	13	7.69
		391	9	10	10.00	10	10.00	10	10.00	10	10.00
		502	7	8	12.50	9	22.22	8	12.50	8	12.50

Table3.jpg

Balancing of Cost-Oriented U-Type General Resource-Constrained Assembly Line: New Constraint Programming Models

Status:

Version 1

Abstract

Figures

Full Text

Tables

Supplementary Files

Status:

Version 1