文摘

我们考虑一个单机调度问题与外包选择的环境中,下游的成本信息是可以通过一些信息共享技术。分配给这个职位的到期日期是不同的从传统的到期日期。每一个工作都可以处理内部或外包。注意,为节省费用,尽可能多的到期日期的外包工作应该被取消。内部工作需要逐步迟到惩罚成本,导致外包成本和外包工作。因此,目标是最小化点球和外包总成本减去总利润从节约成本。我们表明,问题是弱赋权和调查一些可以用多项式来解决案件。由于高动态编程的复杂性,我们开发了启发式,通过数值实验验证他们的表现。

1。介绍

信息共享已经被称为一个有效的工具,使供应链各方相互协调(1,2]。许多场景,利用信息共享的能力可能根据供应链的特点。在这篇文章中,我们考虑制造商想要安排他们处理问题的工作,这样的成本载体以及她自己的同时最小化成本。我们假设决策者,即。,manufacturer, is well aware of the cost structure of her carrier by some information sharing technologies.

一般来说,制造商在当前的商业环境正在委托生产的一部分,分包商和第三方物流供应商,分别。通过这样的外包,制造商可以准时发货到消费者,减少运营成本,使其组织更加灵活。因此,正确使用外包可以使公司更有竞争力3,4),这为我们提供了动机与一个外包的选择要考虑生产调度问题(5,6,7]。

在这篇文章中,我们考虑一个单机调度问题,这样的工作可以由内部资源或直接处理外包给一个分包商。为内部工作,分配一个到期日期,取决于工作的顺序,逐步可以发生迟到惩罚成本。到期日期可以解释为一个特定的卡车的到达时间由一个独立的载体。注意,这些截止日期不是具体工作,但是具体的位置,这些被称为截止日期广义的到期日期(GDD) (8]。这反映了情况下,承运人的卡车定期访问工厂根据计划时间表和拿起不是一个特定的产品,但它是在卡车到达时完成。在这种情况下,卡车的到达时间可以被视为到期日期。当一些工作决心被外包,它假定尽可能多的到期日期应该取消外包工作的数量。特别是,我们假设任何到期日期都可以取消。这不同于Gerstl和Mosheiov[的取消政策9),截止日期在nonincreasing订单取消。

正如一开始所提到的,制造商的目标是最小化包含两个组件:一个对自己的成本和其他成本的载体。对于一个给定的截止日期,生产是外包的成本费用。承运人的成本,相反,等待成本之间的差异是由于完成工作和后期的利润由于取消了约会。足够的取消通知从制造商比预产期早使承运人改变相应的资源,例如,卡车和司机。因此,我们假设的取消约会产生利润而不是成本。注意,对于制造商,所有信息载体可用的一些信息共享技术。

备注1。节3,我们将展示我们的问题是,pseudopolynomial弱赋权时间算法。此外,在节4中,我们将介绍一些可以用多项式来解决案件。所有这些结果还持有的情况下取消约会会增加成本,而不是利润。
本文的主要贡献是建立问题的计算复杂性和它的变体,和设计启发式的有效性是通过数值实验验证的。从业人员来说,他们认为我们的问题是一个适当的模型问题,可以用多项式来解决案件,启发式可以提供一些指导方针,解决自己的问题。特别是,制造商可以使他们的生产计划与运营商或其他下游公司。这种做法会导致降低运输成本以及管理费用的制造商(10]。
GDD的调度问题是引入的大厅(8]。在大厅8和大厅等。11)研究,病例的计算复杂度等各种性能的最大迟到,总加权完工时间,总加权迟到,和加权的迟缓的乔布斯是建立在不同的机器环境,比如一台机器,并行机器,和商店。然而,单机调度问题,最小化总加权数迟到的工作已被证明是np难Sriskandarajah [12和元13),和强np难度高,元14]。Mosheiov,或者15)认为并行相同的机器上的问题最小化最大迟到和总迟到。他们表明,安排最短处理时间(SPT)下令执行非常好。崔和公园(16)考虑单机调度GDD和相同的到期日期间隔最小化加权的早期和缓慢的工作。他们发现,问题是强np困难,也没有ρ光纤固定值的算法 。Gerstl和Mosheiov9)被认为是两个单机调度问题与GDD和拒绝选项拒绝总成本最小的目标加上最大迟到或总迟到。他们表明,两个机器的问题是弱赋权和发展启发式的性能通过数值实验验证了。我们所知,Gerstl Mosheiov [9)是唯一考虑的调度问题GDD和外包的选择。
本文的其余部分组织如下。部分2定义了我们的问题。节3,我们证明我们的软弱的np困难问题。部分3提出了一些条件,让我们可以用多项式来解决问题。节4,我们开发启发式进行数值实验。最后,在节6,我们提出我们的结束语。

2。符号和定义问题

在本节中,我们介绍了本文中使用符号和正式定义我们的问题。

让和处理时间和成本的外包工作 ,分别。让是th到期日期和被取消的利润为 。我们假设 。让 是一个时间表,这样内部工作的数量h和 在哪里是我内部的工作分配到期日期。不失一般性,假设

让的完成时间我th公司内部工作σ计算的

让迟到的惩罚成本函数的工作分配 ,这是定义为 在哪里是一个给定的阈值。不失一般性,假设

这逐步迟到处罚成本一直被认为在运输和半导体制造领域(17- - - - - -20.]。

然后,我们的问题是找到一个时间表σ最小化 在哪里和是外包的设置工作,取消了截止日期,分别;也就是说,

让我们的问题被称为问题页。

命题1。存在一个最优调度的内部工作由SPT的顺序排序。

证明。命题1将立即从标准两两交换计划。
从今以后,我们只考虑日程安排满足命题1。

3所示。计算复杂度

在本节中,我们表明,P是弱np难问题。对于np困难的证明,我们使用相同的基数分区(ECP)问题,可以表示如下:给定一组的元素,一个绑定 ,和大小为每个元素 , 可以分割成两个不相交的集和这样

不失一般性,假设任何子集与 ,

引理1。P是np难问题,即使:(我)每一个阶跃函数只有两个时间间隔, (2)之间的时间间隔连续到期日期是相同的,也就是说, 在哪里是一个给定的阈值。

证明。鉴于项目问题的一个实例,我们可以构造一个实例问题如下。有 工作与 让和 这种减少可以在多项式时间内进行。从今以后,我们表明,解决项目问题的存在当且仅当存在一个时间表σ对于P问题 。
假设存在一个解决方案 该项目问题。然后,我们可以构造一个时间表 这样(我)内部工作的数量(2) 工作的SPT序列在吗 ,在哪里工作是第一次工作,根据命题吗1(3) 让和 。注意,对 , 自 , 和 , 不平等(15)和(16)表明,不存在于迟缓的内部工作 。此外,根据上面的减排方案, 因此,通过不平等(17), 假设存在一个时间表 对于P问题 。让 自 , 和没有迟到工作中存在这意味着工作是第一个由命题内部工作1。

权利要求1。 。

证明。关系(20.), 。因此,索赔1认为只有通过证明 。假设 。然后,持有,通过假设(9),我们有 这是一个矛盾。

要求2。 。

证明。自和 , 假设 。然后, 由不平等(23),我们有 和工作 变得迟缓的。这是一个矛盾。
让和 。然后,和成为该项目问题的解决方案。
从今以后,为简单起见,假设

引理2。P在pseudopolynomial时间可以解决问题。

证明。我们减少问题P (SP)的最短路径问题。让 和 分别是源和汇节点。让 节点表示:(我)这工作 需要外包(2)截止日期在 不得不被取消(3)内部工作的总处理时间 是C如果和 ,然后让 被连接到 长度为 如果和 ,然后让 被连接到水槽节点与长度 目标是找到SP从源到汇节点。在减少SP问题,观察到的节点数量 ,和每个节点有即将离任的弧线。因为减少了SP的问题是无环的图,SP可以解决的问题的算法Ahuja et al。21]。

定理1。P是弱np难问题。

证明。定理1将立即从前题1和2。

4所示。可以用多项式来解决案件

在本节中,我们介绍三个可以用多项式来解决案件。

定理2。P是可以用多项式来解决问题如果处理时间是相同的,也就是说, , 。

证明。我们将证明定理2通过减少问题P的SP问题这样的节点总数是有界的n。让 和 分别是源和汇节点。让 节点表示。(我)这工作 需要外包(2)截止日期在 不得不被取消(3)内部工作的总处理时间 是如果和 ,然后让 被连接到 长度为 如果和 ,然后让 被连接到水槽节点与长度 目标是找到SP从源到汇节点。在减少SP问题,观察到的节点数量 ,和每个节点有即将离任的弧线。因为减少了SP的问题是无环的图,SP可以解决的问题的算法Ahuja et al。21]。

定理3。P是可以用多项式来解决问题,如果(我)之间的时间间隔连续到期日期是相同的,也就是说, 在哪里是一个给定的阈值;(2) 为每一个 。

证明。以最优的时间表,迟到的处罚总成本是零的观察序列在SPT内部工作秩序。在此基础上观察,我们将证明定理3通过减少问题P的加权匹配问题。
建立一个图表 这样(我) 和 (2)为每条边 , 和为和 ,边缘的重量 是计算 目标是找到的边缘它的总重量是最大化。注意,如果边缘 ,然后在一个最优调度问题的P,工作l是外包的,到期日期吗取消了。降低加权匹配的问题可以解决匈牙利法。

定理4。鉴于 ,它是确定可以用多项式来解决 最小化对问题P。

证明。我们将证明定理4通过减少问题P的SP问题这样的节点数量是有界的n。让工作的完成时间 。让和 分别是源和汇节点。让 节点表示。(我)截止日期在 不得不被取消(2)内部工作被分配给如果和 ,然后让 被连接到 长度为 如果和 ,然后让 被连接到水槽节点与长度 。如果 ,然后让 被连接到水槽节点与长度 目标是找到SP从源到汇节点。在减少SP问题,观察到的节点数量 ,和每个节点有即将离任的弧线。因为减少了SP的问题是无环的图,SP可以解决的问题的算法Ahuja et al。21]。

5。启发式

在本节中,由于引理的高动态编程的复杂性2,我们提出三个启发式。我们进行数值实验来评估每个启发式。启发式H1是基于启发式Gerstl和Mosheiov [9]。首先,启发式H1重视工作被外包和到期日期提前被取消和构造新的时间表删除工作和到期日期的顺序优先从最初的时间表。然后,启发式H1构造中选择最好的安排时间表。启发式H1的详细描述如下。

5.1。启发式H1

步骤1。获得两个序列和通过测序nonincreasing订单的工作和 ,分别和一个序列ς通过测序nonincreasing订单的到期日期 。步骤2。集 步骤3。构造 在哪里和子序列由吗和通过删除工作和 ,分别。步骤4。返回这样

启发式H1可以提高房地产的定理4。而不是在步骤3的启发式H1, H2启发式分配根据算法在截止日期的证明定理4。详细过程如下。

5.2。启发式H2

步骤1。获得两个序列和通过测序nonincreasing订单的工作和 ,分别。步骤2。集 步骤3。构造 在哪里的子序列通过删除工作和获得的序列是通过应用定理的方法吗4当 。步骤4。返回这样

与启发式H1和H2,启发式H3构造新的时间表通过优化删除工作和到期日期从最初的时间表基于定理4。然后,启发式H3构造中选择最好的安排时间表。启发式H3的详细描述如下。

5.3。启发式H3

步骤1。集 和 ,在哪里 步骤2。构造 在哪里和子序列由吗π和θ通过删除工作j和到期日期 ,分别。步骤3。找到 这样 步骤4。集 , , , 和 。步骤5。如果 ,然后设置 。步骤6。如果 ,然后返回和停止;否则,转到第2步。

6。实验结果

评估启发式H1-H3的性能,我们进行了数值试验与随机生成的实例在不同的设置。我们实现了Python语言的启发式。实现pseudopolynomial时间算法中引入引理2使用Python NetworkX包。我们所有的实验进行笔记本电脑32 GB的RAM和4.00 GHz处理器。

6.1。实例

所有实例都分类对工作岗位的数量(n)和密度广义的到期日期所定义的Gerstl和Mosheiov9]。更具体地说,我们认为 ,和80个工作岗位。作业处理时间间隔和外包成本是随机生成的和 ,分别。广义到期日期生成均匀的间隔 ,在哪里 。我们考虑的情况下 ,和1.0。取消约会的利润是随机生成的时间间隔 。最后,对于迟到的惩罚成本介绍了部分1, , ,和δ是处理时间的标准差的工作。我们生成30为每个实例 。

6.2。结果

评估解决方案的质量通过启发式H1-H3,我们比较这三种解决方案与最优的解决方案,即通过引理pseudopolynomial时间算法2。为实例 ;然而,最佳的解决方案并不是由于缺乏计算机内存可用。

表1显示了目标的时间表通过应用启发式H1-H3值和最优算法下的实例设置 。H3优于其他启发式在所有情况下,尤其是,找到最佳的解决方案的实例。因此,启发式H3是最好的三个启发式。

表2比较了三个启发式优化算法的计算时间。启发式H1是最快的,因为它只是各种工作和到期日期根据预定义的措施。启发式H3排名第二,但它需要重复的枚举。相反,虽然启发式H1, H2类似于启发式展品更长的计算时间比启发式H1自SP作为子程序需要解决的问题。

结果显示在表中1和2,启发式H3可能是最具竞争力的替代最优算法和启发式。实际上,可以得出类似的结论 设置不同的β值。

密度的影响广义到期日期(所控制α在我们的实验)也报道在表3。有趣的是,启发式H3发现所有30实例的最优解 。

在表4我们调查的影响β。注意,启发式H1不考虑β在它的实现,从而发现相同的解决方案,不管β。相反,启发式H2和H3考虑β因此寻找不同的解决方案不同β值。

表5演示的平均每个设置客观值n和α。我们发现表演与以前的结果一致。

最后,我们报告增加计算时间对工作岗位的数量。表6显示的平均值和标准差计算时间的实例 。启发式H1最快找到解决方案,几乎没有变化,因为它简单排序工作。相反,启发式H2的计算时间显示大幅增加就业数量的增加,因为它使用了一个SP路径子例程。启发式H3的计算时间隔的H1和H2。

7所示。结束语

各方之间的信息共享在供应链提供了一个机会为供应链成员彼此协调。在本文中,我们考虑一个对齐的生产和运输时间表问题可以建模为一个单机调度问题与广义到期日期和外包的选择。迟到和外包成本发生因为内部和外包工作,分别和节约成本来自于取消了约会。目标是最小化总外包和取消成本减去总受益于节约成本。我们发现问题是np难,即使每一个阶跃函数只有两个间隔,我们开发了一个pseudopolynomial时间算法。由于高pseudopolynomial时间算法的复杂性,然而,我们开发了三个启发式和验证他们的性能进行数值试验在不同的设置。这些研究结果可用于设计和实施生产计划考虑下游企业生产和运输的对齐。

数据可用性

使用的数据来支持本研究的发现可以从相应的作者。

的利益冲突

作者宣称没有利益冲突。

确认

这项工作是支持的2019个研究Myongji大学的基金。