Communication Papers of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS)

DOI: http://dx.doi.org/10.15439/2024F7665

Citation: Communication Papers of the 19th Conference on Computer Science and Intelligence Systems (FedCSIS), M. Bolanowski, M. Ganzha, L. Maciaszek, M. Paprzycki, D. Ślęzak (eds). ACSIS, Vol. 41, pages 131–138 (2024)

Full text

Abstract. We deal here with the synchronization of a resource production process and the consumption of those resources by machines used in order to run a set of jobs. Those machines require resources, stored inside tanks with limited storage capacities. Resources are produced by a Resource Lot Sizer player, under some economic costs and technical constraints. Both the Resource Lot Sizer and the Job Scheduler interact through transfer transactions that involve specific constraints, making the synchronization between both processes become an issue. Resulting scheduling problem appears as a multi-stage Lot Sizing problem, that typically arises in contexts where the resource is some renewable energy (hydrogen, electricity, …) required by the jobs and stored inside tanks or batteries embedded into the machines (vehicles or robots). Since this problem, taken as a whole, is complex, we suppose here that its parallel machine scheduling side has been treated and that what remains to be done is to schedule the production of the resource and the transfer transactions. We first cast resulting SLSS: Synchronized Lot Sizing/Scheduling problem into the MILP format, perform a structural analysis of the transfer transactions and handle resulting MILP\_SLSS model through Branch and Cut. Next we come to our main contribution that consists in reformulating the SLSS problem as a path search problem set in a specific Transfer space and handling through a filtered adaptation of the A* algorithm.

References

1. F. Bendali, J. Mailfert, E. Mole-Kamga, A. Quilliot, H. Toussaint, Pipelining dynamic programming process in order to synchronize energy production and consumption, Proc. 2020 FEDCSIS WCO Conf., p 303-306, 2020. doi.org/10.15439/978-83-955416-7-4.
2. Biel K., Glock C. H.: Systematic literature review of decision support models for energy-efficient production planning. Computers and Industrial Engineering, 101, pp. 243-259, (2016). https://doi.org/10.1016/j.cie.2016.08.021.
3. Clark A. Almada-Lobo B., Almeder C.: , J.: Lot sizing and scheduling: Industrial extensions and research opportunities. International Journal of Production Research 49-9, p 2457-2461 (2011). https://doi.org/10.1080/00207543.2010.532908.
4. Erdelic T., Caric T., Lalla-Ruiz E.: A Survey on the Electric Vehicle Routing Problem: Variants and Solution Approaches.Journal of Advanced Transportation Volume 2019. Article ID 5075671; https://doi.org/10.1155/2019/5075671.
5. S. Fidanova, O. Roeva, M. Ganzha, Ant colony optimization algorithm for fuzzy transport modelling, Proc. 2020 FEDCSIS WCO Conference, p 237-240, 2020. doi.org/10.15439/978-83-955416-7-4
6. Franck A.: On chain and antichain families of a partially ordered set. Journal of Combinatorial Theory. Series B 29-2, p 176-184 (1980). https://doi.org/10.1016/0095-8956(80)90079-9.
7. Hart P. E., Nilsson N. J., Bertram R.: A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4-2, p 100-107 (1968). https://doi.org/10.1109/TSSC.1968.300136.
8. Irani S, Pruhs K.: Algorithmic problems in power management. ACM SIGACT News 36-2, p 63-76 (2005). http://dx.doi.org/10.1145/1067309.1067324.
9. K. Stoilova, T. Stoilov, Bi-level optimization application for urban traffic management, Proc. 2020 FEDCSIS WCO Conf., p 327-336, 2020. doi.org/10.15439/978-83-949419-5-6.