Minimization of the total weighted earliness of tasks on a single machine
Keywords:
календарне планування; оптимізація; допустимий розклад; багаторівнева модель управлінняAbstract
We consider the problem of building a feasible schedule for the execution of tasks with various due dates on a single machine. The optimality criteria are double fold: the first is the latest time of the machine start, the second is minimization of the total weighted earliness of tasks in a feasible schedule where the criteria are given in a lexicographic order. That is, the starting time of the machine is as late as possible, and when this condition is fulfilled, the minimum possible value of the total weighted earliness of tasks is reached on a feasible schedule. The authors showed that this problem is qualitatively harder than the above formulated problem with equal positive weights. This paper proposes an exact method based on building of feasible solution trees. Fundamentally new are the formulated restrictions on the set of vertices of each level and the theoretically substantiated efficient rules for cutting branches. The rules are implemented in a statistically significant way already at the first levels of the feasible solution tree. The practical value of the proposed method is illustrated by the possibility of its application in a multi-level model of innovative project management at the last level of its hierarchy.
References
Wang, Z.Y., Lu, C. (2021). An integrated job shop scheduling and assembly sequence planning approach for discrete manufacturing. Journal of Manufacturing Systems, 61, 27-44. doi: 10.1016/j.jmsy.2021.08.003
Li, X., Gao, L. (2020). Introduction for Integrated Process Planning and Scheduling. In: Effective Methods for Integrated Process Planning and Scheduling. Engineering Applications of Computational Methods, vol 2. Springer, Berlin, Heidelberg. doi: 10.1007/978-3-662-55305-3_1
Tuo, L., Dai, L., Chen, X. (2014). Scheduling of Discrete Manufacturing Process for Energy Saving. In: Applied Mechanics and Materials (Vols. 556–562, pp. 4248–4254). Trans Tech Publications, Ltd. doi: 10.4028/www.scientific.net/amm.556-562.4248
Kulcsár, G., & Kulcsárné, F.M. (2009). Solving multi-objective production scheduling problems using a new approach. Production Systems and Information Engineering, A Publication of the University of Miskolc, 5, 81–94.
Pavlov, A.A. (2021). Long-Term Operational Planning of a Small-Series Production Under Un¬cer¬tainty (Theory and Practice). In: Hu, Z., Petoukhov, S., Dychka, I., He, M. (eds) Advances in Com¬puter Science for Engineering and Education III. ICCSEEA 2020. Advances in Intelligent Systems and Computing, vol 1247, pp. 167-180. Springer, Cham. doi: 10.1007/978-3-030-55506-1_15
Pavlov, A.A., Khalus, E.A., Borysenko, I.V. (2019). Planning Automation in Discrete Systems with a Given Structure of Technological Processes. In: Hu, Z., Petoukhov, S., Dychka, I., He, M. (eds) Advances in Computer Science for Engineering and Education. ICCSEEA 2018. Advances in Intelligent Systems and Computing, vol 754, pp. 177-185. Springer, Cham. doi: 10.1007/978-3-319-91008-6_18
Pavlov, A.A., Misura, E.B., Melnikov, O.V., Mukha, I.P. (2019). NP-Hard Scheduling Problems in Planning Process Automation in Discrete Systems of Certain Classes. In: Hu, Z., Petoukhov, S., Dychka, I., He, M. (eds) Advances in Computer Science for Engineering and Education. ICCSEEA 2018. Advances in Intelligent Systems and Computing, vol 754, pp. 429-436. Springer, Cham. doi: 10.1007/978-3-319-91008-6_43
Zgurovsky, M.Z., Pavlov, A.A. (2019). Optimal Scheduling for Two Criteria for a Single Machine with Arbitrary Due Dates of Tasks. In: Combinatorial Optimization Problems in Planning and Decision Making. Studies in Systems, Decision and Control, vol 173, pp. 17-38. Springer, Cham. doi: 10.1007/978-3-319-98977-8_2
Zgurovsky, M.Z., Pavlov, A.A. (2019). Algorithms and Software of the Four-Level Model of Planning and Decision Making. In: Combinatorial Optimization Problems in Planning and Decision Making. Studies in Systems, Decision and Control, vol 173, pp. 407-518. Springer, Cham. doi: 10.1007/978-3-319-98977-8_9
