﻿ 带有退化维修和交货期窗口的加工时间分别可控的单机排序问题 Single-Machine Due-Window Assignment and Scheduling with Discretely Controllable Job Processing Times and a Deteriorating Rate-Modifying Activity

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

Copyright © 2017 by author and Hans Publishers Inc.

1. 引言

2. 问题描述

3. 问题

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

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

4. 问题

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

(2) 如果，则

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

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

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