Operations Research and Fuzziology
Vol.07 No.01(2017), Article ID:19805,9 pages
10.12677/ORF.2017.71001

Single-Machine Due-Window Assignment and Scheduling with Discretely Controllable Job Processing Times and a Deteriorating Rate-Modifying Activity

Lei Zhang

School of Mathematics and Systems Science, Shenyang Normal University, Shenyang Liaoning

Received: Feb. 4th, 2017; accepted: Feb. 21st, 2017; published: Feb. 24th, 2017

ABSTRACT

In this paper, we consider single-machine due-window assignment and scheduling with discretely controllable job processing times and a deteriorating rate-modifying activity. Each job has multiple processing times to be selected and different processing times are associated with different costs. In addition, we can schedule a deteriorating rate-modifying activity in order to reduce the total cost. We consider two versions of the problem, in the first version, all the jobs share a common due-window and in the second version, each job has their own due-window. The objective is to determine the optimal job sequence, schedule the deteriorating rate-modifying activity and the due-window, so as to minimize the total cost. We provide polynomial-time algorithms for the considered problems.

Keywords:Scheduling, Single-Machine, Discretely Controllable Job Processing Times, Deteriorating Rate-Modifying Activity, Due-Window

带有退化维修和交货期窗口的加工时间 分别可控的单机排序问题

张蕾

沈阳师范大学数学与系统科学学院,辽宁 沈阳

收稿日期:2017年2月4日;录用日期:2017年2月21日;发布日期:2017年2月24日

摘 要

本文讨论了带有退化维修和交货期窗口的加工时间分别可控的单机排序问题。每个工件有多个可能的加工时间,不同的加工时间会产生不同的费用。为了提高机器的生产效率,进行一次退化维修。考虑了两个不同的问题:所有工件有一个共同的交货期窗口;每个工件有属于自己的交货期窗口。目标是确定最优的工件加工顺序、维修活动位置、交货期窗口位置以及极小化总费用函数,给出了多项式时间算法,证明了该问题是多项式时间可解。

关键词 :排序,单机,加工时间分别可控,退化维修,交货期窗口

Copyright © 2017 by author and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在带有交货期窗口的排序问题中,若工件在交货期窗口外完工,则会产生相应的惩罚;若工件在交货期窗口内完工,则不会产生惩罚。Mosheiov和Sarig [1] 研究了带有交货期窗口和维修活动的单机排序问题,通过对不同情况的讨论,给出了多项式时间算法。Liu等 [2] 考虑了带有交货期窗口和加工时间是关于资源的凸函数模型的单机排序问题。Yang等 [3] 研究了带有可控加工时间和多窗口的排序问题。

近年来,对加工时间分别可控的问题的研究越来越多。Chen等 [4] 研究了加工时间分别可控的单机排序问题,通过对几个不同目标函数的分析,分别给出了多项式时间算法。Li等 [5] 对带有维修活动的加工时间分别可控的单机排序问题进行了研究,证明了该问题是多项式时间可解的。

本文考虑了带有交货期窗口和退化维修的加工时间分别可控的单机排序问题。目标是确定最优的工件加工顺序、交货期窗口位置、维修活动位置以及极小化总费用函数。

2. 问题描述

设有个工件在一台机器上加工,所有工件零时刻到达,机器在同一时间只可加工一个工件。工件个可能加工时间,其中是基本加工时间,是最小可能加工时间。是可能加工时间对应的费用,我们规定。为了提高机器的加工效率,进行一次退化维修,维修时间是关于开始维修时间的线性函数,其中是开始维修时间,是维修率。若工件在维修活动后进行加工,可能加工时间为,其中

对于一个给定的排序定义为工件的完工时间。若工件在维修活动前进行加工,定义为工件的实际加工时间。若工件在维修活动后进行加工,定义为工件的实际加工时间。所以有。当工件的实际加工时间为或者时,则会产生相应的费用。现在有两种情况,第一种情况,所有工件有一个共同的交货期窗口。第二种情况,每个工件都有自己的交货期窗口,其中是固定的,且。在这两种情况中,工件的提前、延误完工时间分别定义为:。定义二元函数为:

如果,则,否则

如果,则,否则

我们需要确定工件的加工顺序、最优的窗口位置和窗口大小、维修位置以及维修时间费用函数:。目标函数为。其中,分别为提前、延误、窗口开始时间、窗口大小单位费用。

引用三参数表示法将两个问题分别表示成:

表示退化维修活动,表示加工时间分别可控。

3. 问题

本节中,所有工件有一个共同的交货期窗口,为了提高机器的生产效率,可进行一次维修活动。经过以下的计算、分析,可以极小化总费用函数,确定最优的工件加工顺序、窗口位置、维修位置。

引理1:由文献 [6] 问题最优排序具有以下性质:

(1) 每个工件的加工不可中断,机器无空闲状态,第一个工件在零时刻开始加工;

(2)的最优值等于的最优值等于,其中

引理2:由文献 [1] 最优排序存在于以下几种情况:

情况1:维修活动并未发生;

情况2:维修活动发生在开始时间;

情况3:维修活动发生在第个工件完工后。

设排序为定义为工件排在第个位置,我们分三种情况讨论问题。

情况一维修活动并未发生,定义为目标函数

其中

定义为工件放在位置处所产生的费用:

则该问题可以转化为指派问题:

情况二维修发生在开始时间,定义为目标函数

其中

定义为工件放在位置处所产生的费用:

则该问题可以转化为指派问题:

情况三维修活动发生在第个工件完工后,定义为目标函数

其中

定义为工件放在位置处所产生的费用:

则该问题可以转化为指派问题:

定理1:问题在情况一、情况二中的计算复杂性为,在情况三中的计算复杂性为

证明:在情况一、情况二中,每个工件有个可能的加工时间,对于每个可能的加工时间,该问题都可以转化为指派问题,指派问题的计算复杂性为,因此整个过程的计算复杂性为。情况三中,在以上两种情况的基础上,最多存在个可能的维修位置,因此整个过程的计算复杂性为

4. 问题

本节中,每个工件都有属于自己的交货期窗口,为了提高机器的生产效率,进行一次维修活动,经过本节的计算、分析,可以确定最优的工件加工顺序、窗口位置、维修位置以及极小化总费用函数。Mosheiov和Oron [7] 、Mor和Mosheiov [8] 和Wu等 [9] 给出了一些引理,容易验证,这些引理依然适用于本节的问题。

引理3:问题最优排序具有以下性质:

(1) 每个工件的加工不可中断,机器无空闲状态,第一个工件在零时刻开始加工;

(2) 如果,则

如果,则

(3) 在最优排序中,,其中

引理4:最优排序存在于以下几种情况:

情况1:维修活动并未发生;

情况2:维修活动发生在开始时间;

情况3:维修活动发生在第个工件完工之后,其中

设排序为定义为工件排在第个位置,我们分三种情况讨论问题。

情况一维修活动并未发生,定义为目标函数

其中

定义为工件放在位置处所产生的费用:

则该问题可以转化为指派问题:

情况二维修发生在开始时间,定义为目标函数

其中

定义为工件放在位置处所产生的费用:

则该问题可以转化为指派问题:

情况三维修活动发生在第个工件完工之后,其中定义为目标函数

其中

定义为工件放在位置处所产生的费用:

则该问题可以转化为指派问题:

定理2:问题在情况一、情况二中的计算复杂性为,在情况三中的计算复杂性为

证明:在情况一、情况二中,每个工件有个可能的加工时间,对于每个可能的加工时间,该问题都可以转化为指派问题,指派问题的计算复杂性为,因此整个过程的计算复杂性为。情况三中,在以上两种情况的基础上,最多存在个可能的维修位置,因此整个过程的计算复杂性为

5. 结论

本文讨论了带有交货期窗口和维修活动的加工时间分别可控的单机排序问题。研究了两种不同类型的交货期窗口,分别从三种不同的维修位置进行了计算、分析,证明了这些问题在多项式时间内是可解的。

文章引用

张 蕾. 带有退化维修和交货期窗口的加工时间分别可控的单机排序问题
Single-Machine Due-Window Assignment and Scheduling with Discretely Controllable Job Processing Times and a Deteriorating Rate-Modifying Activity[J]. 运筹与模糊学, 2017, 07(01): 1-9. http://dx.doi.org/10.12677/ORF.2017.71001

参考文献 (References)

  1. 1. Mosheiov, G. and Sarig, A. (2009) Scheduling a Maintenance Activity and Due-Window Assignment on a Single Machine. Computers & Operations Research, 36, 2541-2545. https://doi.org/10.1016/j.cor.2008.10.007

  2. 2. Liu, L., Wang, J.J. and Wang, X.Y. (2016) Single Machine Due-Window Assignment Scheduling with Resource- Dependent Processing Times to Minimize Total Resource Consumption Cost. International Journal of Production Research, 54, 1186-1195. https://doi.org/10.1080/00207543.2015.1056323

  3. 3. Yang, D.L., Lai, C.J. and Yang, S.J. (2014) Scheduling Problems with Multiple Due Windows Assignment and Controllable Processing Times on a Single Machine. International Journal of Production Economics, 150, 96-103. https://doi.org/10.1016/j.ijpe.2013.12.021

  4. 4. Chen, Z.L., Lu, Q. and Tang, G.C. (1996) Single Machine Scheduling with Discretely Controllable Processing Times. Operations Research Letters, 21, 69-76. https://doi.org/10.1016/S0167-6377(97)00010-2

  5. 5. Li, J., Li, X. and Luo, W.C. (2016) Single-Machine Scheduling with Discretely Controllable Job Processing Times Subject to a Deteriorating Rate-Modifying Activity. American Journal of Mathematical and Management Science, 35, 194-206. https://doi.org/10.1080/01966324.2016.1149126

  6. 6. Liman, S.D., Panwalkar, S.S. and Thongmee, S. (1998) Common Due Window Size and Location Determination in a Single Machine Scheduling Problem. Journal of the Operational Research Society, 49, 1007-1010. https://doi.org/10.1057/palgrave.jors.2600601

  7. 7. Mosheiov, G. and Oron, D. (2010) Job-Dependent Due-Window Assignment Based on a Common Flow Allowance. Foundations of Computing and Decision Sciences, 35, 185-195.

  8. 8. Mor, B. and Mosheiov, G. (2015) Scheduling a Deteriorating Maintenance Activity and Due-Window Assignment. Computers & Operations Research, 57, 33-40. https://doi.org/10.1016/j.cor.2014.11.016

  9. 9. Wu, Y.B., Wan, L. and Wang, X.Y. (2015) Study on Due-Window Assignment Scheduling Based on Common Flow Allowance. International Journal of Production Economics, 165, 155-157. https://doi.org/10.1016/j.ijpe.2015.04.005

期刊菜单