Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times
Bi-criterion single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times
复制标题
DOI：
10.1057/jors.2016.14
复制
发表时间：
2016-09
影响因子：
3.6
通讯作者：
Yunqiang Yin;Dujuan Wang;T. Cheng;Chin-Chia Wu
中科院分区：
文献类型：
--
作者：
Yunqiang Yin;Dujuan Wang;T. Cheng;Chin-Chia Wu
本文讨论了具有共同流量和资源依赖加工时间的单机排序和交货期窗口分配问题。具有公共流量余量的交货期窗口分配是指每个工件都有一个与工件相关的交货期窗口，其开始时间和结束时间分别等于其实际加工时间加上所有工件共享的与工件无关的参数。每个作业的处理时间可以通过额外的资源分配来控制，该额外的资源分配是分配给作业的公共连续可分资源的量的线性函数。考虑两个标准，其中一个标准是一个综合成本，包括作业提前，加权拖期作业数，和交货期窗口分配成本，而另一个标准是资源消耗成本。四个不同的模型被认为是治疗的两个标准。结果表明，将两个准则合并为一个准则的模型下的问题是多项式可解的，而其它三个模型下的问题都是NP-难的，并给出了它们的最优解.两个多项式可解的情况下，也确定和调查。最后，随机生成的实例进行数值研究，以评估所提出的算法的性能。
This paper addresses single-machine scheduling and due-window assignment with common flow allowances and resource-dependent processing times. Due-window assignment with common flow allowances means that each job has a job-dependent due window, the start time and finish time of which are equal to its actual processing time plus individual job-independent parameters shared by all the jobs, respectively. The processing time of each job can be controlled by extra resource allocation as a linear function of the amount of a common continuously divisible resource allocated to the job. Two criteria are considered, where one criterion is an integrated cost consisting of job earliness, weighted number of tardy jobs, and due-window assignment cost, while the other criterion is the resource consumption cost. Four different models are considered for treating the two criteria. It is shown that the problem under the model where the two criteria are integrated into a single criterion is polynomially solvable, while the problems under the other three models are allNP-hard and an optimal solution procedure is developed for them. Two polynomially solvable cases are also identified and investigated. Finally, numerical studies with randomly generated instances are conducted to assess the performance of the proposed algorithms.