Minimization of total energy consumption in an m-machine flow shop with an exponential time-dependent learning effect

doi:10.15302/J-FEM-2018042

Front. Eng

2018, Vol. 5

Issue (4) : 487-498 https://doi.org/10.15302/J-FEM-2018042

RESEARCH ARTICLE

Minimization of total energy consumption in an m-machine flow shop with an exponential time-dependent learning effect

Lingxuan LIU¹, Zhongshun SHI², Leyuan SHI³(

)

¹. Department of Industrial Engineering & Management, Peking University, Beijing 100871, China
². Department of Industrial & Systems Engineering, University of Wisconsin-Madison, WI, USA
³. Department of Industrial Engineering & Management, Peking University, Beijing 100871, China; Department of Industrial & Systems Engineering, University of Wisconsin-Madison, WI, USA

Download: PDF(218 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

Abstract

This study investigates an energy-aware flow shop scheduling problem with a time-dependent learning effect. The relationship between the traditional and the proposed scheduling problem is shown and objective is to determine a job sequence in which the total energy consumption is minimized. To provide an efficient solution framework, composite lower bounds are proposed to be used in a solution approach with the name of Bounds-based Nested Partition (BBNP). A worst-case analysis on shortest process time heuristic is conducted for theoretical measurement. Computational experiments are performed on randomly generated test instances to evaluate the proposed algorithms. Results show that BBNP has better performance than conventional heuristics and provides considerable computational advantage.

Keywords flow shop energy-aware scheduling learning effect nested partition worst-case error bound

Corresponding Author(s): Leyuan SHI

Just Accepted Date: 28 August 2018 Online First Date: 08 November 2018 Issue Date: 29 November 2018

Cite this article:

Lingxuan LIU,Zhongshun SHI,Leyuan SHI. Minimization of total energy consumption in an m-machine flow shop with an exponential time-dependent learning effect[J]. Front. Eng, 2018, 5(4): 487-498.

URL:

https://academic.hep.com.cn/fem/EN/10.15302/J-FEM-2018042
https://academic.hep.com.cn/fem/EN/Y2018/V5/I4/487

Fig.1 BBP procedure

Fig.2 BBS procedure

$n$	$a$	SPT		NEH		FL		BBNP
$n$	$a$	mean	max	mean	max	mean	max	mean	max
9	0.7	13.8	40	2.25	9.15	0.1	1.73	0	0
9	0.8	13.2	30.3	3.13	17.6	0.076	0.626	0	0
9	0.9	13.6	34.6	2.81	13.2	0.058	0.777	0	0.01
10	0.7	15.8	34.9	2.19	10	0.16	2.74	0	0.01
10	0.8	16.9	38.8	2.49	16.9	0.099	1.62	0	0.015
10	0.9	16.6	37	1.63	8.35	0.141	1.57	0	0
11	0.7	15.8	34.4	3.82	11.4	0.104	1.15	0.067	1.246
11	0.8	13.7	30.2	2.38	9.24	0.281	2.36	0	0.015
11	0.9	14.8	31.9	1.68	6.43	0.403	3.67	0.133	1.617
12	0.7	15.6	34.2	1.84	6.33	0.153	2.23	0.011	0.124
12	0.8	16.9	39.2	1.81	5.41	0.347	3.12	0.084	1.016
12	0.9	15.6	31.9	2.21	8.28	0.356	3.87	0.104	1.246
13	0.7	17.7	35.4	2.38	13.7	0.385	4.15	0.184	2.039
13	0.8	16.6	31.5	2.41	7.08	0.359	2.18	0.101	0.998
13	0.9	16.8	29.3	2.69	8.52	0.254	2.97	0.125	1.028
14	0.7	11.9	24.5	1.84	7.47	0.105	1.23	0.092	0.926
14	0.8	13.4	21.7	2.28	8.6	0.296	2.27	0.104	1.638
14	0.9	13.3	21.5	2.29	8.12	0.187	2.16	0.067	0.102

Tab.1 Error gap (%) of BBNP and heuristic algorithms for

m = 3

$n$	$a$	SPT		NEH		FL		BBNP
$n$	$a$	mean	max	mean	max	mean	max	mean	max
9	0.7	14.8	40.8	2.5	10.5	0.49	3.32	0.308	3.31
9	0.8	13.8	27.5	4.26	12.1	0.762	4.62	0.314	2.05
9	0.9	15.3	36.2	3.45	12.1	0.773	2.94	0.284	2.12
10	0.7	17.4	29.5	3.5	16.4	0.75	3.07	0.454	3.31
10	0.8	17.6	34.4	3.19	11.1	0.976	5.28	0.402	3.2
10	0.9	16.6	28.3	3.18	11.5	0.447	3.44	0.333	2.98
11	0.7	18	38.3	4.11	19	0.733	3.06	0.438	2.39
11	0.8	16.8	31.7	2.48	9.07	0.964	4.51	0.698	4.9
11	0.9	17.9	42.2	2.77	8.06	0.648	3.31	0.276	1.39
12	0.7	18.9	29	3.28	10.9	1.26	5.48	1.1	5.31
12	0.8	20.1	38.8	5.39	12.3	1.03	6.01	0.585	2.79
12	0.9	15.8	32.4	3.57	11.5	0.558	2.35	0.322	1.86
13	0.7	19.7	42.9	3.46	14.1	1.15	3.7	0.542	2.63
13	0.8	18.9	38.8	2.83	8.68	0.172	1.78	0.132	1.51
13	0.9	16.5	34.6	2.15	9.69	0.576	4.15	0.299	2.07
14	0.7	18.9	30.6	2.9	9	0.866	4.62	0.774	3.7
14	0.8	19.6	38.2	4.21	9.38	1.33	8.43	0.99	4.34
14	0.9	16.7	30.9	2.9	12.8	0.559	2.68	0.392	2.4

Tab.2 Error gap (%) of BBNP and heuristic algorithms for

m = 5

$n$	$a$	Frequency of maximum
$n$	$a$	LB (1)	LB (2)	LB (3)
9	0.7	0.36	0.37	0.27
9	0.8	0.39	0.33	0.28
9	0.9	0.33	0.34	0.33
10	0.7	0.34	0.31	0.35
10	0.8	0.29	0.35	0.36
10	0.9	0.35	0.31	0.34
11	0.7	0.25	0.41	0.34
11	0.8	0.42	0.35	0.23
11	0.9	0.31	0.33	0.36
12	0.7	0.27	0.35	0.38
12	0.8	0.33	0.25	0.42
12	0.9	0.4	0.36	0.24
13	0.7	0.35	0.27	0.38
13	0.8	0.32	0.36	0.32
13	0.9	0.35	0.35	0.3
14	0.7	0.41	0.3	0.29
14	0.8	0.31	0.35	0.34
14	0.9	0.21	0.42	0.37

Tab.3 Results of domination of different LB calculations for partial schedule (

m = 3

)

$n$	$a$	$E (S P T) E (A R B)$		$E (N E H) E (A R B)$		$E (F L) E (A R B)$		$E (B B N P) E (A R B)$
$n$	$a$	mean	max	mean	max	mean	max	mean	max
20	0.7	0.8211	0.9519	0.782	0.9242	0.724	0.8728	0.7148	0.8501
20	0.8	0.804	0.9259	0.7657	0.8989	0.7018	0.8396	0.688	0.8016
20	0.9	0.8107	0.9358	0.7721	0.9086	0.7028	0.8456	0.6916	0.8334
40	0.7	0.8214	0.9406	0.7823	0.9132	0.7027	0.8432	0.677	0.7954
40	0.8	0.7869	0.9366	0.7494	0.9093	0.726	0.8655	0.6751	0.8153
40	0.9	0.7973	0.9239	0.7594	0.897	0.6903	0.8432	0.6815	0.8358
60	0.7	0.8144	0.9409	0.7756	0.9135	0.7027	0.8524	0.6885	0.8251
60	0.8	0.8096	0.9456	0.771	0.9181	0.7022	0.8531	0.6751	0.8165
60	0.9	0.8073	0.9125	0.7689	0.886	0.6901	0.8216	0.6745	0.7703
80	0.7	0.8175	0.9591	0.7785	0.9312	0.7137	0.8722	0.6568	0.7869
80	0.8	0.799	0.9326	0.761	0.9054	0.6788	0.8164	0.6575	0.8317
80	0.9	0.7825	0.9007	0.7453	0.8745	0.6728	0.8359	0.6527	0.8047
100	0.7	0.7159	0.8807	0.6818	0.8551	0.6794	0.8571	0.6216	0.8094
100	0.8	0.7827	0.8968	0.7455	0.8707	0.6673	0.8058	0.6464	0.7764
100	0.9	0.7399	0.8936	0.7047	0.8675	0.6159	0.8282	0.6015	0.7978

Tab.4 Computational results of the heuristics for large-size instances (

m = 5

)

1	Agrawal P, Rao S (2014). Energy-aware scheduling of distributed systems. IEEE Transactions on Automation Science and Engineering, 11(4): 1163–1175 https://doi.org/10.1109/TASE.2014.2308955
2	Artigues C, Lopez P, Haït A (2009). Scheduling under energy constraints. In: International Conference on Industrial Engineering and Systems Management (IESM 2009)
3	Biskup D (1999). Single-machine scheduling with learning considerations. European Journal of Operational Research, 115(1): 173–178 https://doi.org/10.1016/S0377-2217(98)00246-X
4	Chan S H, Lam T W, Lee L K (2013). Scheduling for weighted flow time and energy with rejection penalty. Theoretical Computer Science, 470: 93–104 https://doi.org/10.1016/j.tcs.2012.11.021
5	Cheng T E, Wang G (2000). Single machine scheduling with learning effect considerations. Annals of Operations Research, 98(1–4): 273–290 https://doi.org/10.1023/A:1019216726076
6	Gao F, Liu M, Wang J J, Lu Y Y (2017). No-wait two-machine permutation flow shop scheduling problem with learning effect, common due date and controllable job processing times. International Journal of Production Research, (2): 1–9
7	Garey M R, Johnson D S (1979). Computers and Intractability (Vol. 29).New York: WH Freeman
8	Gonzalez T, Sahni S (1978). Preemptive scheduling of uniform processor systems. Journal of the Association for Computing Machinery, 25(1): 92–101 https://doi.org/10.1145/322047.322055
9	Johnson S M (1954). Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics, 1(1): 61–68 (NRL) https://doi.org/10.1002/nav.3800010110
10	Koulamas C, Kyparisis G J (2007). Single-machine and two-machine flowshop scheduling with general learning functions. European Journal of Operational Research, 178(2): 402–407 https://doi.org/10.1016/j.ejor.2006.01.030
11	Kuo W H, Hsu C J, Yang D L (2012). Worst-case and numerical analysis of heuristic algorithms for flowshop scheduling problems with a time-dependent learning effect. Information Sciences, 184(1): 282–297 https://doi.org/10.1016/j.ins.2011.08.018
12	Lee W C, Wu C C (2004). Minimizing total completion time in a two-machine flowshop with a learning effect. International Journal of Production Economics, 88(1): 85–93 https://doi.org/10.1016/S0925-5273(03)00179-8
13	Lee Y C, Zomaya A Y (2010). Energy efficient resource allocation in large scale distributed systems. In: Proceedings of Distributed Computing and Applications to Business Engineering and Science (DCABES), 2010 Ninth International Symposium on IEEE. 580–583
14	Li G, Wang X Y, Wang J B, Sun L Y (2013). Worst case analysis of flow shop scheduling problems with a time-dependent learning effect. International Journal of Production Economics, 142(1): 98–104 https://doi.org/10.1016/j.ijpe.2012.10.015
15	Liu G S, Yang H D, Cheng M B (2017). A three-stage decomposition approach for energy-aware scheduling with processing-time- dependent product quality. International Journal of Production Research, 55(11): 3073–3091 https://doi.org/10.1080/00207543.2016.1241446
16	Liu J, Chou P H, Bagherzadeh N, Kurdahi F (2001). Power-aware scheduling under timing constraints for mission-critical embedded systems. In: Proceedings of the 38th Annual Design Automation Conference. 840–845
17	Pei J, Cheng B, Liu X, Pardalos P M, Kong M (2017). Single-machine and parallel-machine serial-batching scheduling problems with position-based learning effect and linear setup time. Annals of Operations Research, (3): 1–25
18	Pei J, Liu X, Fan W, Pardalos P M, Lu S (2017). A hybrid BA-VNS algorithm for coordinated serial-batching scheduling with deteriorating jobs, financial budget, and resource constraint in multiple manufacturers. Omega, 82: 55–69 https://doi.org/10.1016/j.omega.2017.12.003
19	Rudek R (2011). Computational complexity and solution algorithms for flowshop scheduling problems with the learning effect. Computers & Industrial Engineering, 61(1): 20–31 https://doi.org/10.1016/j.cie.2011.02.005
20	Shi L, Ólafsson S (2000). Nested partitions method for global optimization. Operations Research, 48(3): 390–407 https://doi.org/10.1287/opre.48.3.390.12436
21	Shi L, Ólafsson S, Chen Q (2001). An optimization framework for product design. Management Science, 47(12): 1681–1692 https://doi.org/10.1287/mnsc.47.12.1681.10243
22	Smutnicki C (1998). Some results of the worst-case analysis for flow shop scheduling. European Journal of Operational Research, 109(1): 66–87 https://doi.org/10.1016/S0377-2217(97)00139-2
23	Sun L H, Cui K, Chen J H, Wang J, He X C (2013). Research on permutation flow shop scheduling problems with general position-dependent learning effects. Annals of Operations Research, 211(1): 473–480 https://doi.org/10.1007/s10479-013-1481-6
24	Wang J B, Wang D, Wang L Y, Lin L, Yin N, Wang W W (2009). Single machine scheduling with exponential time-dependent learning effect and past-sequence-dependent setup times. Computers & Mathematics with Applications, 57(1): 9–16 https://doi.org/10.1016/j.camwa.2008.09.025
25	Wang J B, Wang J J (2014). Flowshop scheduling with a general exponential learning effect. Computers & Operations Research, 43: 292–308 https://doi.org/10.1016/j.cor.2013.09.001
26	Wang J B, Xia Z Q (2005). Flow-shop scheduling with a learning effect. Journal of the Operational Research Society, 56(11): 1325–1330 https://doi.org/10.1057/palgrave.jors.2601856
27	Wang X Y, Zhou Z, Zhang X, Ji P, Wang J B (2013). Several flow shop scheduling problems with truncated position-based learning effect. Computers & Operations Research, 40(12): 2906–2929 https://doi.org/10.1016/j.cor.2013.07.001
28	Webb G K (1994). Integrated circuit (IC) pricing. Journal of High Technology Management Research, 5(2): 247–260 https://doi.org/10.1016/1047-8310(94)90005-1
29	Wright T P (1936). Factors affecting the cost of airplanes. Journal of the Aeronautical Sciences, 3(4): 122–128 https://doi.org/10.2514/8.155
30	Wu C C, Lee W C (2009). A note on the total completion time problem in a permutation flowshop with a learning effect. European Journal of Operational Research, 192(1): 343–347 https://doi.org/10.1016/j.ejor.2007.10.003
31	Wu T, Shi L, Duffie N A (2010). An HNP-MP approach for the capacitated multi-item lot sizing problem with setup times. IEEE Transactions on Automation Science and Engineering, 7(3): 500–511 https://doi.org/10.1109/TASE.2009.2039134
32	Xu J, Lin W C, Wu J, Cheng S R, Wang Z L, Wu C C (2016). Heuristic based genetic algorithms for the re-entrant total completion time flowshop scheduling with learning consideration. International Journal of Computational Intelligence Systems, 9(6): 1082–1100 https://doi.org/10.1080/18756891.2016.1256572
33	Xu Z, Sun L, Gong J (2008). Worst-case analysis for flow shop scheduling with a learning effect. International Journal of Production Economics, 113(2): 748–753 https://doi.org/10.1016/j.ijpe.2007.11.002

[1]	Zhongshun SHI, Zewen HUANG, Leyuan SHI. Two-stage scheduling on batch and single machines with limited waiting time constraint[J]. Front. Eng, 2017, 4(3): 368-374.

Viewed

Full text

Abstract

Cited

Shared

Discussed