﻿ 带有工期窗口和凸资源分配的单机排序问题 Single-Machine Scheduling with Due-Window Assignment and Convex Resource Allocation

Vol.07 No.04(2018), Article ID:24710,10 pages
10.12677/AAM.2018.74055

Single-Machine Scheduling with Due-Window Assignment and Convex Resource Allocation

Shi Li, Chengxin Luo

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

Received: Apr. 12th, 2018; accepted: Apr. 21st, 2018; published: Apr. 28th, 2018

ABSTRACT

We consider a single machine scheduling problem with learning effect and deterioration effect. The actual processing time of a job is a convex function of the resource amount allocated to it. All jobs have a common due-window. The actual processing time of each job is a convex function dependent on the workload of the job, its starting time and its allocation of non-renewable resource. We consider three models. For the first we aim to minimize the weighted costs of earliness, tardiness, the starting time of the common due-window, the size of the due-window, the makespan and the total completion time. For the second, we constrain the total resource amount to minimize the weighted costs of earliness, tardiness, the starting time of the common due-window, the size of the due-window, the makespan and the total completion time. For the third, we are subject to the constraint that the total cost with early and tardy cost is less than or equal to a fixed amount to minimize the total resource. We show that the problems are polynomial solvable by transforming them into matching problems. Three optimal algorithms are given.

Keywords:Scheduling, Resource Allocation, Deterioration Effect, Learning Effect, Matching Problem, Due-Window

1. 引言

2. 问题描述

(1)

(2)

(3)

3. 最优算法

3.1. 最优解性质

(4)

(5)

1) 如果，则

2) 如果，则

3) 如果，则

4) 如果，则

3.2. 最优算法

,

(6)

(7)

(8)

(10)

(11)

(12)

(13)

, , (14)

(15)

(16)

(17)

(18)

4. 结论

Single-Machine Scheduling with Due-Window Assignment and Convex Resource Allocation[J]. 应用数学进展, 2018, 07(04): 446-455. https://doi.org/10.12677/AAM.2018.74055

1. 1. Biskup, D. (2008) A State-of-the-Art Review on Scheduling with Learning Effect. European Journal of Operational Research, 188, 315-329. https://doi.org/10.1016/j.ejor.2007.05.040

2. 2. Gawiejnowicz, S. (2008) Time-Dependent Scheduling. Springer, Berlin.

3. 3. Shabtay, D. and Steiner, G. (2007) A Survey of Scheduling with Controllable Processing Times. Discrete Applied Mathematics, 155, 1643-1666. https://doi.org/10.1016/j.dam.2007.02.003

4. 4. Wang, X.-R. and Wang, J.-J. (2013) Single-Machine Scheduling with Convex Resource Dependent Processing Times and Deteriorating Jobs. Applied Mathematical Modelling, 37, 2388-2393. https://doi.org/10.1016/j.apm.2012.05.025

5. 5. Wang, X.-Y. and Wang, J.-J. (2013) Single-Machine Due Date Assignment Problem with Deteriorating Jobs and Resource-dependent Processing Times. International Journal of Advanced Manufacturing Technology, 67, 255-260. https://doi.org/10.1007/s00170-013-4771-x

6. 6. Wang, J.B., Wang, M.Z. and Ji, P. (2012) Scheduling Jobs with Processing Times Dependent on Position, Staring Time and Allotted Resource. Asia-Pacific Journal of Operational Research, 29, 1250030.

7. 7. Lu, Y.-Y., Li, G., Wu, Y.-B. and Ji, P. (2014) Optimal Due-Date Assignment Problem with Learning Effect and Resource-Dependent Processing Times. Optimization Letters, 8, 113-127. https://doi.org/10.1007/s11590-012-0467-7

8. 8. Cheng, T.C.E., Kang, L.Y. and Ng, C.T. (2004) Due-Date Assignment and Single Machine Scheduling with Deteriorating Jobs. Journal of the Operational Research Society, 55, 198-203. https://doi.org/10.1057/palgrave.jors.2601681

9. 9. Gordon, V.S. and Tarasevich, A.A. (2009) A Note: Common Due Date Assignment for a Single Machine Scheduling with the Rate-Modifying Activity. Computers & Operations Research, 36, 325-328. https://doi.org/10.1016/j.cor.2007.10.008

10. 10. Sun, L.-H., Cui, K., Chen, J.-H. and Wang, J. (2016) Due Date Assignment and Convex Resource Allocation Scheduling with Variable Job Processing Times. International of Production Research, 54, 3551-3560. https://doi.org/10.1080/00207543.2015.1083628

11. 11. Li, G., Luo, M.L., Zhang, W.J. and Wang, X.Y. (2015) Single-Machine Due-Window Assignment Scheduling Based on Flow Allowance, Learning Effect and Resource Allocation. International Journal of Production Research, 53, 1228-1241. https://doi.org/10.1080/00207543.2014.954057

12. 12. 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

13. 13. Wang, J.B. and Wang, J.J. (2015) Research on Scheduling with Job-Dependent Learning Effect and Convex Resource-Dependent Processing Times. International Journal of Production Research, 53, 5826-5836. https://doi.org/10.1080/00207543.2015.1010746

14. 14. Wang, J.-B., Liu, M.-Q., Yin, N. and Ji, P. (2017) Scheduling Jobs with Controllable Processing Time, Truncated Job-Dependent Learning and Deteriortion Effects. Journal of Industrial and Management Optimization, 13, 1025-1039.

15. 15. Mor, B. and Mosheiov, G. (2012) Scheduling a Maintenance Activity and Due Window Assignment Based on Common Flow Allowance. International Journal of Production Economics, 135, 222-230. https://doi.org/10.1016/j.ijpe.2011.07.013

16. 16. Graham, R.L., Lawler, E.L., Lenstra, J.K. and Rinnooy Kan, A.H.G. (1979) Optimization and Approximation Indeterministic Sequencing and Scheduling. A Survey. Annals of Discrete Mathematics, 5, 287-326. https://doi.org/10.1016/S0167-5060(08)70356-X

17. 17. Hardy, G.H., Littlewood, J.E. and Polya, G. (1967) Inequalities. Cambridge University Press, Cambridge.