文摘

本文认为单机due-window作业调度问题与位置相关的权重,权重只取决于他们的位置在一个序列。目标是最小化总加权惩罚早熟,迟到,due-window开始时间,due-window大小的所有工作。最优的属性问题,然后提供了一个多项式时间算法来解决这个问题。的扩展提供的问题是假设一般位置相关处理时间。

1。介绍

一般来说,在调度理论中,交货期窗口也job-dependent如果由客户(即。,因为常量)或决策变量(即。due-window作业)。一个due-window工作由due-window定义开始的时间吗和due-window完成时间 ,即。,the due-window ,和due-window大小 。准时制(JIT)生产方法和调度理论,设置合适的交货期窗口挑战(见龚et al。1),Janiak et al。2耿,et al。3])。在文献中,三个非常受欢迎的due-window分配方法进行了研究:常见due-window (CON-DW)分配方法(泻湖et al。4,5):所有的工作都分配一个常见due-window,即。有一个共同的due-window,所有的工作 ,在哪里 , ,due-window大小的所有工作 ,和两个和决策变量。在文献中,大多数研究认为CON-DW分配方法,例如,Mosheiov和Sarig [6解决一个极大极小CON-DW分配问题,目标是最小化最大的成本在早熟,迟到,due-window开始时间,due-window大小。他们证明了单机和两流水车间可以在多项式时间内解决的问题。他们也证明了平行的情况下相同的机器和统一的机器是赋权。阴et al。7)考虑交货批调度问题的可转让的常见due-window在单个机器上。阴et al。8]研究了单机调度问题CON-DW作业和批量交货成本。刘等人。9)被认为是单机CON-DW作业调度问题恶化的就业机会。的加权和早熟、迟到和due-window位置损失最小化,他们提出了一个多项式时间算法来解决这个问题。王先生和王10)被认为是单机资源分配调度问题与学习效果和CON-DW任务。松弛due-window (SLK-DW)分配方法(Mosheiov,或者11)) , ,和 ,在哪里是正常的处理时间的工作吗和和决策变量。王等人。12)被认为是单机SLK-DW作业调度问题恶化的就业和学习效果。霁et al。13)被认为是单机成组技术SLK-DW作业调度问题。阴et al。14),阴et al。15王,et al。16]认为SLK-DW作业调度与资源分配问题(可控加工时间)。铁道部和Mosheiov17)认为SLK-DW分配比例的流水车间调度问题。不同交货期窗口”(DIF-DW)分配方法:假设这个工作有一个due-window ,在哪里 和 表示的开始时间和结束时间due-window,分别。的due-window大小的工作是 ,和两个和决策变量。王等人。12]认为DIF-DW作业调度问题恶化的就业和学习效果。

在最近的一篇论文,王et al。18认为CON-DW和SLK-DW与位置相关的权重分配方法,即。,the weight does not correspond with the job but with the position in which some job is scheduled. They proved that both these due-window assignment methods with position-dependent weights can be solved in polynomial time, respectively.“due-window作业的调度有很多实际应用。例如,due-window可能反映一个装配环境中产品的组件应该准备在一个时间间隔,以避免临时延误或商店,几个工作构成一个客户的订单。很明显,一个宽due-window增加供应商的生产和交付的灵活性。然而,大型due-window和延迟作业完成减少供应商的竞争力和客户服务水平”(杨et al。19])。这是自然和有趣的继续王等人的作品。18),但研究DIF-DW位置相关权重分配调度问题。本文给出的贡献如下:(1)调度问题是派生的结构性质;(2)的总加权惩罚早熟,迟到,due-window开始时间,due-window大小的乔布斯的最小化可以在多项式时间内解决;和(3)进一步扩展模型的一般位置相关处理时间。我们提到的读者调查Janiak et al。2)调度问题(CON-DW、SLK-DW DIF-DW)交货期窗口。

本文的其余部分组织如下。节2我们制定这个问题。部分3给出了一些结果和最优政策的提出问题。提出的问题给出的延伸部分4。最后,给出了结论和未来的工作。

2。问题描述

一组工作 需要一台机器上处理。所有可用的独立工作在时间为零,和抢占是不允许的。对于一个给定的序列,我们假设工作有一个due-window ,在哪里 ( )表示due-window的开始时间(完成时间), 。due-window大小的工作被定义为 ,和和所有工作都是决策变量。正常的处理时间的工作用(即。,the processing time without being influenced by any factor), 。对于一个给定的序列,让工作的完成时间 。目的是找到最优交货期窗口的起始时间,交货期窗口的大小,工作的顺序这样,以下措施是最小化: 在哪里表示的工作安排th位置, ( )表示位置相关的体重(即。、体重不符合这个职位的工作,但一些工作计划),( )的单位成本( ), 的earliness-tardiness工作吗( ),和

使用延用符号(Graham et al。20.]),问题是学习 。王等人。18)考虑单机调度问题常见due-window (CON-DW)和松弛due-window (SLK-DW)作业。他们证明了问题和可以解决的时间,分别。

3所示。主要结果

很明显,存在一个最优序列没有任何机器空闲时间之间的处理工作,和序列中的第一份工作开始时间为零。

引理1。存在一个最优序列,这样 。

证明。我们认为这个最优属性相矛盾的两种情况:我:如果 ,然后工作的总成本是 我们的转变这样左边 ,我们有 因此,我并非最优due-window任务。案例二:如果 ,然后工作的总成本是 我们的转变和这样左边 ,我们有 因此,案例二世并非最优due-window任务。
总结,我们有 。

引理2。对于一个给定的序列 ,最优due-window位置和为工作可以得到如下:(1)当 ,然后设置 (2)当 ,然后设置 (3)当 ,然后设置 和

证明。(1)当 和 ,我们有 从引理1,我们考虑以下两种情况:我:如果 ,然后工作的总成本是 案例二:如果 ,然后工作的总成本是总结,如果 ,然后设置 。
同样,例(2)和(3)可以证明的。

引理3。对于一个给定的序列 ,最优due-window位置和为工作可以得到如下:(1)当 ,然后设置 ,在哪里 (2)当 ,然后设置 ,在哪里 (3)当 ,然后设置 和 ,在哪里 (4)当 ,然后设置 和 ,在哪里 和

证明。类似于证明引理的证明2。

引理4。问题的最优序列可以通过测序得到的工作在不减少的顺序吗 ,即。,the smallest processing time (SPT) first rule.

证明。的前题1- - - - - -3的目标函数可以转换为以下三种情况:(1) ;(2) ;和(3) 。三个案例,很容易验证(两两交换方法)测序的工作在不减少的顺序是最优的。
让 , ,和 ;然后, 在哪里 和

备注1。很明显, 是一个递减函数 ;从哈代等。21),可获得最优序列的SPT规则,它是一样的引理4。
的前题1- - - - - -4,可以提出了一个多项式时间算法问题。

定理1。算法1解决问题在时间。

证明。可以保证最优的前题1- - - - - -4。在算法1,第一步需要时间的SPT规则;步骤2和3可以执行时间。因此,算法的总时间1是 。
为了说明算法1的问题 ,我们提出以下实例。

例1。数据如下: , 。
现在,我们可以解决这个问题根据算法1如下:步骤1:根据引理4最优序列 步骤2:为最优序列 ,所有工作的完成时间 ,和最优due-window位置和为每个工作表1步骤3:最佳due-window尺寸 ( ), , , , , , , , , ,和 ,和目标函数 。

4所示。一个扩展

在本节中,这个问题是扩展到一般位置相关处理时间的设置。让的实际处理时间 ;在一般位置相关处理时间设置,实际的处理时间是 如果是分配到的位置 , 。因此,包含一个矩阵的输入问题 工作岗位的价值。Biskup [22]介绍了job-independent学习效应模型 ,在哪里 也学习指数(见王et al。23])。Mosheiov和西德尼24]介绍了job-dependent学习效应,即 ,在哪里 job-dependent学习指数的工作吗 。王等人。25]介绍了截断job-dependent学习效应,即 ,在哪里 是一个截断参数。我们提到的读者调查Azzouz et al。26在调度问题与学习效果。

从(7),我们有 在哪里是由(9)。

从(10),最优问题的序列 可以通过解决以下分配问题: 在哪里 ,是由(9),

基于上述分析,解决问题的过程 可以概括如下。

定理2。算法2解决问题 在时间。

证明。最优性保证了前题1- - - - - -3和上面的分析。在算法2,第一步需要时间的SPT规则;步骤2和3可以执行时间。因此,算法的总时间2是 。为了说明算法2的问题 ,我们提出以下实例。

例2。数据如下: , 。job-dependent处理时间在表中2。

5。结论和未来的工作

本研究解决due-window (DIF-DW)作业调度问题的考虑下位置相关权重。目标是确定最优序列,最优due-window位置和大小,这样总处罚(包括早熟,迟到,due-window起始时间,所有工作和due-window大小)是最小化。这是证明,可以在多项式时间内解决的问题。该模型也扩展到一般位置相关处理时间,和多项式时间的解决方案。进一步扩展正在考虑上述设置中存在的问题 - - - - - -机流水车间和 - - - - - -相同的(无关)并行机器(Hsu和廖27]),研究了调度与two-agent依赖资源的释放时间(刘,段28]),或调查调度rate-modifying活动恶化效应(雪、张29日])。

步骤1:由(9),我们有 , , , , , , ,和 。根据分配问题(11),最优序列 。步骤2:为最优序列 ,所有工作的完成时间 ,和最优due-window位置和为每个工作表3。步骤3:最佳due-window尺寸 ( ),和目标函数 。

数据可用性

没有数据被用来支持本研究。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作得到了辽宁省自然科学基金(2020 - ms - 233)。