Exact Methods and Heuristics for Order Acceptance Scheduling Problem under Time-of-Use Costs and Carbon Emissions
Source abstract
Abstract
This research focuses on an Order Acceptance Scheduling (OAS) problem on a single machine under time-of-use (TOU) tariffs and taxed carbon emissions periods with the objective to maximize total profit minus tardiness penalties and environmental costs. Due to the NP-hardness of the considered problem especially in presence of sequence-dependent setup-times, two fix-and-relax (FR) heuristics based on different time-indexed (TI) formulations are proposed. A metaheuristic based on the Dynamic Island Model (DIM) framework is also employed to tackle this optimization problem. These approached methods show promising results both in terms of solution quality and solving time compared to state-of-the-art exact solving approaches.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Scheduling and Optimization Algorithms · Supply Chain and Inventory Management · Advanced Manufacturing and Logistics Optimization
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
Computer Laboratory and Digital Society (LIST3N), University of Technology of Troyes, 10000 Troyes, France
Funding
Conseil régional du Grand Est · Conseil départemental de l'Aube
References (59)
Show source-provided references
1. International Monetary Fund (2020). World Economic Outlook, April 2020, Intl Monetary Fund.
2. (2021, April 17). Industry-Energy Efficiency 2020-Analysis-IEA. Available online: www.iea.org/reports/energy-efficiency-2020/industry.
3. (2020, October 04). Emissions Trading: Greenhouse Gas Emissions Reduced by 8.7% in 2019|Climate Action. Available online: https://ec.europa.eu/clima/news/emissions-trading-greenhouse-gas-emissions-reduced-87-2019_en.
4. (2020, October 04). GDP Growth (% Annual), World Bank National Accounts Data, and OECD National Accounts Data Files. Available online: https://data.worldbank.org/indicator/NV.IND.TOTL.ZS.
5. A framework to minimise total energy consumption and total tardiness on a single machine10.1080/19397030802257236 ↗
6. Energy efficiency, robustness, and makespan optimality in job-shop scheduling problems10.1017/S0890060415000335 ↗
7. Energy-conscious flow shop scheduling under time-of-use electricity tariffs10.1016/j.cirp.2014.03.011 ↗
8. Industry 4.0: Revolution or Evolution?
9. Order acceptance and scheduling decisions in make-to-order systems10.1016/j.ijpe.2010.02.002 ↗
10. Resource-constrained scheduling with hard due windows and rejection penalties10.1080/0305215X.2015.1120298 ↗
11. Order selection and scheduling with leadtime flexibility10.1080/07408170490447366 ↗
12. Chen, S.H., Liou, Y.C., Chen, Y.H., and Wang, K.C. (2019). Order acceptance and scheduling problem with carbon emission reduction and electricity tariffs on a single machine. Sustainability, 11.10.3390/su11195432 ↗
13. Kahraman, C., Cevik Onar, S., Oztaysi, B., Sari, I., Cebi, S., and Tolga, A. (2020). Order Acceptance Scheduling on a Single Machine with Energy Aspects, Springer. Intelligent and Fuzzy Techniques: Smart and Innovative Solutions.10.1007/978-3-030-51156-2 ↗
14. Candan, C., Goëffon, A., Lardeux, F., and Saubion, F. (2013, January 13–17). Non stationary operator selection with island models. Proceedings of the Fifteenth Annual Conference on Genetic and Evolutionary Computation Conference-GECCO ’13, Prague, Czech Republic.10.1145/2463372.2463559 ↗
15. A review of energy-efficient scheduling in intelligent production systems10.1007/s40747-019-00122-6 ↗
16. Optimizing the production scheduling of a single machine to minimize total energy consumption costs10.1016/j.jclepro.2013.12.024 ↗
17. MILP models for energy-aware flexible job shop scheduling problem10.1016/j.jclepro.2018.11.021 ↗
18. Carbon-efficient scheduling of flow shops by multi-objective optimization10.1016/j.ejor.2015.05.019 ↗
19. Energy cost minimization for unrelated parallel machine scheduling under real time and demand charge pricing10.1016/j.jclepro.2018.10.048 ↗
20. Liao, X., Zhang, R., and Chiong, R. (December, January 27). Multi-objective optimization of single machine scheduling with energy consumption constraints. Proceedings of the 2017 IEEE Symposium Series on Computational Intelligence (SSCI), Honolulu, HI, USA.10.1109/SSCI.2017.8285403 ↗
21. Flow shop scheduling with peak power consumption constraints10.1007/s10479-012-1294-z ↗
22. An efficient greedy insertion heuristic for energy-conscious single machine scheduling problem under time-of-use electricity tariffs10.1016/j.jclepro.2016.03.150 ↗
23. Complexity analysis of energy-efficient single machine scheduling problems
24. Solving the energy-efficient job shop scheduling problem: A multi-objective genetic algorithm with enhanced local search for minimizing the total weighted tardiness and total energy consumption10.1016/j.jclepro.2015.09.097 ↗
25. Jiang, T., Zhang, C., Zhu, H., Gu, J., and Deng, G. (2018). Energy-efficient scheduling for a job shop using an improved whale optimization algorithm. Mathematics, 6.10.3390/math6110220 ↗
26. Optimization of production scheduling with time-dependent and machine-dependent electricity cost for industrial energy efficiency10.1007/s00170-013-4749-8 ↗
27. The impact of various carbon reduction policies on green flowshop scheduling10.1016/j.apenergy.2019.04.155 ↗
28. Exact and heuristic algorithms for order acceptance and scheduling with sequence-dependent setup times10.1016/j.cor.2017.09.006 ↗
29. Karwowski, W., Trzcielinski, S., and Mrugalska, B. (2020). Order acceptance and scheduling problem: A proposed formulation and the comparison with the literature. Advances in Manufacturing, Production Management and Process Control, Springer.10.1007/978-3-030-20494-5 ↗
30. Integrating order acceptance decisions with flexible due dates in a production planning model with load-dependent lead times10.1080/00207543.2014.993045 ↗
31. Order acceptance and scheduling: A taxonomy and review10.1016/j.ejor.2010.09.042 ↗
32. A survey on offline scheduling with rejection10.1007/s10951-012-0303-z ↗
33. Order acceptance and scheduling with consideration of service level10.1007/s10479-016-2277-2 ↗
34. Project selection with discounted returns and multiple constraints10.1016/0377-2217(95)00156-5 ↗
35. A branch and price solution approach for order acceptance and capacity planning in make-to-order operations10.1016/j.ejor.2011.01.002 ↗
36. A learning and optimizing system for order acceptance and scheduling10.1007/s00170-015-8321-6 ↗
37. Order acceptance using genetic algorithms10.1016/j.cor.2008.04.010 ↗
38. A tabu search algorithm for order acceptance and scheduling10.1016/j.cor.2010.09.018 ↗
39. Generalized order acceptance and scheduling problem with batch delivery: Models and metaheuristics10.1016/j.cor.2021.105414 ↗
40. Green manufacturing: Order acceptance and scheduling subject to the budgets of energy consumption and machine launch10.1016/j.jclepro.2019.119300 ↗
41. Bouzid, M., Masmoudi, O., and Yalaoui, A. (2020, January 12–14). Time-indexed formulations for the order acceptance scheduling problem under energy aspects. Proceedings of the 13ème Conférence Francophone de Modélisation, Optimisation et Simulation-MOSIM’20, Agadir, Maroc.
42. Absi, N., Chrétienne, P., and Kedad-Sidhoum, S. (2005). Modélisation et réSolution de Problèmes de Lot-Sizing à Capacité Finie. [Ph.D. Thesis, Université Paris VI].
43. Lot-sizing in a multi-stage flow line production system with energy consideration10.1080/00207543.2016.1206670 ↗
44. A fix-and-relax heuristic for the single-item lot-sizing problem with a flow-shop system and energy constraints10.1080/00207543.2019.1683249 ↗
45. Surgical scheduling with simultaneous employment of specialised human resources10.1016/j.ejor.2015.04.008 ↗
46. Planning and scheduling operating rooms for elective and emergency surgeries with uncertain duration10.1016/j.orhc.2018.03.006 ↗
47. Modeling and solving a sugarcane harvest front scheduling problem10.1016/j.ijpe.2019.03.009 ↗
48. Machine learning and optimization for production rescheduling in Industry 4.010.1007/s00170-020-05850-5 ↗
49. Scheduling in production, supply chain and Industry 4.0 systems by optimal control: Fundamentals, state-of-the-art and applications10.1080/00207543.2018.1442948 ↗
50. Li, Y., Fadda, E., Manerba, D., Tadei, R., and Terzo, O. (2020, January 6–9). Reinforcement Learning Algorithms for Online Single-Machine Scheduling. Proceedings of the 2020 15th Conference on Computer Science and Information Systems (FedCSIS), Sofia, Bulgaria.10.15439/2020F100 ↗
51. (2021, September 08). Plastic&Rubber 4.0. Piattaforma Tecnologica per la Fabbrica Intelligente (Technological Platform for Smart Factory). Available online: www.gallina.it/plastic-and-rubber.
52. Multi-objective optimization for energy-efficient flexible job shop scheduling problem with transportation constraints10.1016/j.rcim.2019.04.006 ↗
53. Energy-efficient bi-objective single-machine scheduling with power-down mechanism10.1016/j.cor.2017.04.004 ↗
54. A memetic differential evolution algorithm for energy-efficient parallel machine scheduling10.1016/j.omega.2018.01.001 ↗
55. Deb, K., Bhattacharya, A., Chakraborti, N., Chakroborty, P., Das, S., Dutta, J., Gupta, S.K., Jain, A., Aggarwal, V., and Branke, J. (2010). A Dynamic Island-Based Genetic Algorithms Framework, Springer. Simulated Evolution and Learning.10.1007/978-3-642-17298-4 ↗
56. Masmoudi, O., Chehade, H., and Yalaoui, A. (2016). Optimisation de la Planification des Systèmes Industriels en Présence de Contraintes Énergétiques. [Ph.D. Thesis, Université de Technologie de Troyes].
57. Hybrid evolutionary approaches for the single machine order acceptance and scheduling problem10.1016/j.asoc.2016.09.051 ↗
58. Krishnaiah, K., and Shahabudeen, P. (2012). Applied Design of Experiments and Taguchi Methods, PHI Learning Pvt. Ltd.
59. (2021, January 18). Minitab 19.2020.1 (64-Bit) Statistical Software. Available online: www.minitab.com.