A memetic algorithm for energy-efficient scheduling of integrated production and shipping

Figures & data

Table 1. Classification of related energy-efficient scheduling studies.

References	Production environments			With shipping	Energy mechanisms				Objectives	Methods
	S	P	F		On/Off	Speed	TOU	Others
Mouzon, Yildirim, and Twomey (2007)	√				√				Energy+completion time	Dispatching rules
Mouzon and Yildirim (2008)	√				√				Energy + tardiness	Adaptive search metaheuristic
Shrouf et al. (2014)	√				√		√		Energy	Genetic algorithm
Fang et al. (2016)	√					√	√		Energy	Approximation algorithm
Che et al. (2017)	√				√				Energy + tardiness	ε−constraint method
Rubaiee and Yildirim (2019)	√						√		Energy+ completion time	Ant colony optimization
Fang and Lin (2013)		√				√			Energy + tardiness	Particle swarm optimization
Wang, Wang, and Lin (2017)		√						√	Makespan	Heuristics
Shioura et al. (2018)	√	√				√			Energy+ completion time	Theoretical analysis
Wu and Che (2019)		√				√			Energy + makespan	Memetic differential evolution algorithm
Ding, Song, and Wu (2016)			√		√	√			Carbon emissions + makespan	Multi-objective NEH algorithm and iterated greedy algorithm
Mansouri, Aktas, and Besikci (2016)			√			√			Energy + makespan	Constructive heuristic
Luo et al. (2013)			√				√		Energy + makespan	Ant colony optimization
Yan et al. (2016)			√					√	Energy + makespan	Genetic Algorithm
Lei, Gao, and Zheng (2017)			√			√			Energy and tardiness	Teaching-learning-based algorithm
Lu et al. (2017)			√		√				Energy + makespan	Backtracking search algorithm
Li et al. (2018)			√					√	Energy + makespan	Multi-objective optimization algorithm
Meng et al. (2019)			√		√				Energy	Improved genetic algorithm
Zheng et al. (2020)			√				√		Energy + makespan	Multi-objective hybrid ant colony optimisation
Wang et al. (2020)			√		√		√		Energy + makespan	ε−constraint method and meta-heuristics
Gong et al. (2020a)			√						Energy+ makespan + worker cost	Hybrid evolutionary algorithm
Öztop et al. (2020)			√			√			Energy + flowtime	Augmented epsilon-constraint approach
Zhang et al. (2021)			√			√	√		Energy	Tabu search-greedy insertion hybrid algorithm
Yüksel et al. (2020)			√			√			Energy + tardiness	Artificial bee colony, genetic algorithm
This research		√		√	√	√			Energy + makespan	Memetic algorithm

Figure 1. Schematic diagram of the energy-efficient scheduling scheme.

Table

Sets
$M$	Set of unrelated machines, $i\in M$
$N$	Set of jobs, $j,k\in N$
$V$	Set of processing speed modes, $v\in V$
$H$	Set of vehicles, $h\in H$
Parameters
$r_j$	Release time of job $j$, $j\in N$
$t_j$	Processing time of job $j$, $j\in N$
$t{{ }^{\mathrm{\prime }}}_j$	Shipping time of job $j$ from manufacturer to customer
$u_v$	Processing speed factors for different processing speeds, $v\in V$
$t_i^r$	Reset time for machine $i$ per time
$e_{iv}^p$	Processing energy consumed per unit time for machine $i$ at speed mode $v$
$e_i^r$	Reset energy consumed per unit time for machine $i$
$e_i^s$	Standby energy consumed per unit time for machine $i$
$E_{\hspace{0.17em}}^p$	Processing energy consumption
$E_{\hspace{0.17em}}^r$	Reset energy consumption
$E_{\hspace{0.17em}}^s$	Standby energy consumption
$B$	A very large number
$q_j$	Size of job $j$
$Q_h$	Capacity of vehicle $h$
$e{{ }^{\mathrm{\prime }}}_h$	Shipping energy consumed per unit time for vehicle $h$
$E{ }^{\mathrm{\prime }}$	Shipping energy consumption
Decision variables
$C_j$	Completion time of job $j$ in production
${\chi }_{ijk}$	1 if job $j$ immediately precedes job $k$ on machine $i$, and 0 otherwise
${\eta }_{ijv}$	1 if job $j$ is processed on machine $i$ at speed $v$, and 0 otherwise
${\theta }_{ij}$	1 if machine $i$ is reset before processing job $j$, and 0 otherwise
$C{{ }^{\mathrm{\prime }}}_j$	Completion time of job $j$ for shipping
$C{{ }^{\mathrm{\prime }}}_{max}$	The makespan
$U_{hjk}$	1 if job $j$ is immediately dispatched before job $k$ on vehicle $h$, and 0 otherwise
$W_{hj}$	1 if job $j$ is assigned on vehicle $h$, and 0 otherwise

Figure 2. Flowchart of the proposed MA.

Figure 3. Chromosome representation.

Figure 4. Pseudocode for decoding.

Figure 5. Unbiased tournament selection.

Figure 6. Crossover operator.

Figure 7. Hybrid mutation operator.

Figure 8. Pseudocode for heuristic H.

Table 2. MA parameters and their levels in the orthogonal method.

Factors	Factor levels
	1	2	3
Psize	50	100	200
Pc	0.5	0.7	0.9
Pm	0.1	0.3	0.5

Table 3. Orthogonal array and results.

Run No.	Factor levels			CME
	Psize	Pc	Pm
1	1	1	1	5328.8
2	1	2	2	5322.9
3	1	3	3	5316.5
4	2	1	2	5318.4
5	2	2	3	5312.7
6	2	3	1	5326.4
7	3	1	3	5305.4
8	3	2	1	5324.3
9	3	3	2	5313.8

Figure 9. Main effect plot of the MA parameters.

Table 4. Algorithms comparison.

|N|	(|M|,|H|)	GA		AMA		MA_L		MA_L_D
		CME	Time (s)	CME	Time (s)	CME	Time (s)	CME	Time (s)
25	(2, 4)	1848.4	14.9	1840.5	15.5	1847.7	10.7	1846.9	2.8
	(4, 4)	1683.0	15.7	1682.0	15.1	1672.9	14.4	1671.7	7.0
	(8, 4)	1574.5	12.0	1577.5	17.8	1578.0	14.4	1573.2	7.5
50	(2, 4)	3423.3	20.0	3421.4	20.1	3419.0	17.5	3418.8	3.8
	(4, 4)	3028.2	24.6	3034.7	24.7	3011.8	23.0	2986.9	12.3
	(8, 4)	2819.3	28.0	2807.0	28.2	2786.2	24.9	2767.9	21.7
75	(2, 4)	4668.7	26.3	4658.7	30.1	4645.6	23.9	4638.0	5.5
	(4, 4)	4127.6	34.5	4129.1	34.6	4097.5	25.8	4059.3	16.3
	(8, 4)	3840.9	38.6	3826.3	39.2	3788.3	33.3	3792.5	28.0
100	(2, 4)	6449.9	39.0	6452.8	35.1	6442.8	33.0	6440.9	6.6
	(4, 4)	5507.6	44.5	5495.7	44.2	5494.5	39.8	5468.0	23.2
	(8, 4)	5004.6	48.8	4978.1	49.3	4932.3	41.8	4910.1	47.4
150	(2, 4)	10293.6	62.5	10295.0	58.8	10283.1	56.9	10272.4	12.1
	(4, 4)	8991.0	64.7	9018.4	65.0	8923.2	55.7	8904.0	33.2
	(8, 4)	8265.7	68.7	8264.9	69.1	8210.4	59.7	8221.1	65.1
300	(2, 4)	20676.0	124.0	20695.2	124.4	20671.3	110.7	20648.9	19.2
	(4, 4)	17911.1	125.9	17881.2	124.7	17964.9	109.1	17773.9	54.5
	(8, 4)	16,339.8	127.3	16306.1	126.6	16218.0	111.8	16184.4	143.5
Average		7025.2	51.1	7020.3	51.2	6999.3	44.8	6976.6	28.3

Table 5. ANOVA for different problem sizes.

|N|	f0	P-value
25	80.12	0.000
50	69.81	0.000
75	73.89	0.000
100	53.77	0.000
150	59.25	0.000
300	101.08	0.000

Table 6. Energy savings by energy-efficient scheduling with different mechanisms.

|N|	Traditional scheduling (Energy consumption)	Energy-efficient scheduling (Energy consumption/Energy savings)
	No energy optimization	Power-down	Speed-scaling	Both
25	2835.9	2478.1/12.6%	2384.3/16.0%	2308.7/18.6%
50	5352.1	4952.3/7.5%	4654.1/13.0%	4630.3/13.5%
75	8065.1	7511.9/6.9%	7021.8/12.9%	7011.6/13.1%
100	10774.6	10221.8/5.1%	9503.7/11.8%	9500.4/11.8%
150	16164.5	15445.8/4.5%	14422.7/10.8%	14402.7/10.9%
300	21297.4	20602.9/3.3%	18963.0/11%	18947.5/11%
Average energy savings		6.7%	12.6%	13.2%

Figure 10. Pareto frontier with different weight combinations: (a) Problem $|N|$ = 50, (b) Problem $|N|$ = 100 and (c) Problem $|N|$ = 150.

Mouzon, G., M. B. Yildirim, and J. Twomey. 2007. “Operational Methods for Minimization of Energy Consumption of Manufacturing Equipment.” International Journal of Production Research 45 (18–19): 4247–4271. doi:10.1080/00207540701450013.

 Web of Science ®Google Scholar

Mouzon, G., and M. B. Yildirim. 2008. “A Framework to Minimise Total Energy Consumption and Total Tardiness on A Single Machine.” International Journal of Sustainable Engineering 1 (2): 105–116. doi:10.1080/19397030802257236.

 Google Scholar

Shrouf, F., J. Ordieres-Meré, A. García-Sánchez, and M. Ortega-Mier. 2014. “Optimizing the Production Scheduling of a Single Machine to Minimize Total Energy Consumption Costs.” Journal of Cleaner Production 67: 197–207. doi:10.1016/j.jclepro.2013.12.024.

 Web of Science ®Google Scholar

Fang, K., N. A. Uhan, F. Zhao, and J. W. Sutherland. 2016. “Scheduling on a Single Machine under Time-of-use Electricity Tariffs.” Annals of Operations Research 238 (1–2): 199–227. doi:10.1007/s10479-015-2003-5.

 Web of Science ®Google Scholar

Che, A., X. Wu, J. Peng, and P. Yan. 2017. “Energy-efficient Bi-objective Single-machine Scheduling with Power-down Mechanism.” Computers & Operations Research 85: 172–183. doi:10.1016/j.cor.2017.04.004.

 Web of Science ®Google Scholar

Rubaiee, S., and M. B. Yildirim. 2019. “An Energy-aware Multi-objective Ant Colony Algorithm to Minimize Total Completion Time and Energy Cost on a Single-machine Preemptive Scheduling.” Computers & Industrial Engineering 127: 240–252. doi:10.1016/j.cie.2018.12.020.

 Web of Science ®Google Scholar

Fang, K.-T., and B. M. Lin. 2013. “Parallel-machine Scheduling to Minimize Tardiness Penalty and Power Cost.” Computers & Industrial Engineering 64 (1): 224–234. doi:10.1016/j.cie.2012.10.002.

 Web of Science ®Google Scholar

Wang, Y.-C., M.-J. Wang, and S.-C. Lin. 2017. “Selection of Cutting Conditions for Power Constrained Parallel Machine Scheduling.” Robotics and Computer-Integrated Manufacturing 43: 105–110. doi:10.1016/j.rcim.2015.10.010.

 Web of Science ®Google Scholar

Shioura, A., N. V. Shakhlevich, V. A. Strusevich, and B. Primas. 2018. “Models and Algorithms for Energy-efficient Scheduling with Immediate Start of Jobs.” Journal of Scheduling 21 (5): 505–516. doi:10.1007/s10951-017-0552-y.

 Web of Science ®Google Scholar

Wu, X., and A. Che. 2019. “A Memetic Differential Evolution Algorithm for Energy-efficient Parallel Machine Scheduling.” Omega 82: 155–165. doi:10.1016/j.omega.2018.01.001.

 Web of Science ®Google Scholar

Ding, J.-Y., S. Song, and C. Wu. 2016. “Carbon-efficient Scheduling of Flow Shops by Multi-objective Optimization.” European Journal of Operational Research 248 (3): 758–771. doi:10.1016/j.ejor.2015.05.019.

 Web of Science ®Google Scholar

Mansouri, S. A., E. Aktas, and U. Besikci. 2016. “Green Scheduling of a Two-machine Flowshop: Trade-off between Makespan and Energy Consumption.” European Journal of Operational Research 248 (3): 772–788. doi:10.1016/j.ejor.2015.08.064.

 Web of Science ®Google Scholar

Luo, H., B. Du, G. Q. Huang, H. Chen, and X. Li. 2013. “Hybrid Flow Shop Scheduling considering Machine Electricity Consumption Cost.” International Journal of Production Economics 146 (2): 423–439. doi:10.1016/j.ijpe.2013.01.028.

 Web of Science ®Google Scholar

Yan, J., L. Li, F. Zhao, F. Zhang, and Q. Zhao. 2016. “A Multi-level Optimization Approach for Energy-efficient Flexible Flow Shop Scheduling.” Journal of Cleaner Production 137: 1543–1552. doi:10.1016/j.jclepro.2016.06.161.

 Web of Science ®Google Scholar

Lei, D., L. Gao, and Y. Zheng. 2017. “A Novel Teaching-learning-based Optimization Algorithm for Energy-efficient Scheduling in Hybrid Flow Shop.” IEEE Transactions on Engineering Management 65 (2): 330–340. doi:10.1109/TEM.2017.2774281.

 Web of Science ®Google Scholar

Lu, C., L. Gao, X. Li, Q. Pan, and Q. Wang. 2017. “Energy-efficient Permutation Flow Shop Scheduling Problem Using a Hybrid Multi-objective Backtracking Search Algorithm.” Journal of Cleaner Production 144: 228–238. doi:10.1016/j.jclepro.2017.01.011.

 Web of Science ®Google Scholar

Li, J., H. Sang, Y. Han, C. Wang, and K. Gao. 2018. “Efficient Multi-objective Optimization Algorithm for Hybrid Flow Shop Scheduling Problems with Setup Energy Consumptions.” Journal of Cleaner Production 181: 584–598. doi:10.1016/j.jclepro.2018.02.004.

 Web of Science ®Google Scholar

Meng, L., C. Zhang, X. Shao, Y. Ren, and C. Ren. 2019. “Mathematical Modelling and Optimisation of Energy-conscious Hybrid Flow Shop Scheduling Problem with Unrelated Parallel Machines.” International Journal of Production Research 57 (4): 1119–1145. doi:10.1080/00207543.2018.1501166.

 Web of Science ®Google Scholar

Zheng, X., S. Zhou, R. Xu, and H. Chen. 2020. “Energy-efficient Scheduling for Multi-objective Two-stage Flow Shop Using a Hybrid Ant Colony Optimisation Algorithm.” International Journal of Production Research 58 (13): 4103–4120.

 Web of Science ®Google Scholar

Wang, S., X. Wang, F. Chu, and J. Yu. 2020. “An Energy-efficient Two-stage Hybrid Flow Shop Scheduling Problem in a Glass Production.” International Journal of Production Research 58 (8): 2283–2314. doi:10.1080/00207543.2019.1624857.

 Web of Science ®Google Scholar

Gong, G., R. Chiong, Q. Deng, W. Han, L. Zhang, W. Lin, and K. Li. 2020a. “Energy-efficient Flexible Flow Shop Scheduling with Worker Flexibility.” Expert Systems with Applications 141: 112902. doi:10.1016/j.eswa.2019.112902.

 Web of Science ®Google Scholar

Öztop, H., M. F. Tasgetiren, D. T. Eliiyi, Q.-K. Pan, and L. Kandiller. 2020. “An Energy-efficient Permutation Flowshop Scheduling Problem.” Expert Systems with Applications 150: 113279. doi:10.1016/j.eswa.2020.113279.

 Web of Science ®Google Scholar

Zhang, H., Y. Wu, R. Pan, and G. Xu. 2021. “Two-stage Parallel Speed-scaling Machine Scheduling under Time-of-use Tariffs.” Journal of Intelligent Manufacturing 32 (1): 91–112.

 Web of Science ®Google Scholar

Yüksel, D., M. F. Taşgetiren, L. Kandiller, and L. Gao. 2020. “An Energy-efficient Bi-objective No-wait Permutation Flowshop Scheduling Problem to Minimize Total Tardiness and Total Energy Consumption.” Computers & Industrial Engineering 145: 106431. doi:10.1016/j.cie.2020.106431.

 Web of Science ®Google Scholar