A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models
A note on optimization in deteriorating systems using scheduling problems with the aging effect and resource allocation models
复制标题
DOI：
10.1016/j.camwa.2011.06.030
复制
发表时间：
2011-08
期刊：
影响因子：
--
通讯作者：
Agnieszka Rudek;Radosław Rudek
中科院分区：
文献类型：
--
作者：
Agnieszka Rudek;Radosław Rudek
本文研究了具有老化效应和附加资源分配的调度问题。老化现象的一个可测量的结果是，执行一项工作所需的时间增加了，而额外的资源分配允许人们减少它。作为一个可以通过所考虑的模型和算法的应用来描述和优化的退化系统的例子，我们选择酸洗过程，其中金属物品的清洗降低了酸洗（清洗）槽（即含有活性物质的槽）的效率，而加热可以提高效率。我们特别关注这类系统的优化问题，并将其建模为单机调度问题，其中作业处理时间取决于机器的疲劳程度和额外资源的分配。考虑的目标是在给定的资源消耗下最小化时间标准（最大完成时间和最大延迟时间），以及在给定的时间标准下最小化资源消耗。确定了问题的计算复杂度，并证明了其解的性质。在此基础上，我们对所考虑的一些问题构造了最优多项式时间算法。
This paper concerns scheduling problems with the aging effect and additional resource allocation. A measurable result of the aging phenomenon is that the time required to perform a job increases whereas the additional resource allocation allows one to decrease it. As an example of a deteriorating system that can be described and optimized by the application of the models and algorithms considered, we choose the pickling process, where cleaning of metal items decreases the efficiency of the pickling (cleaning) bath (i.e., one containing an active substance), whereas heating it up can improve the efficiency. In particular, we focus on the optimization problems for such systems and model them as single-machine scheduling problems with job processing times dependent on the fatigue of a machine and on the allocation of additional resources. The objectives considered are the minimization of time criteria (the maximum completion time and the maximum lateness) under a given resource consumption as well as the minimization of the resource consumption under given time criteria. The computational complexity of the problems is determined and solution properties are proved. On the basis of these, we construct optimal polynomial time algorithms for some cases of the problems considered.