Top

Journal of Applied Mathematics and Computing

Published in:

01-06-2015 | Original Research

Deteriorating jobs scheduling on a single machine with release dates, rejection and a fixed non-availability interval

Authors: Wei-Xuan Li, Chuan-Li Zhao

Published in: Journal of Applied Mathematics and Computing | Issue 1-2/2015

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

This paper studies single machine scheduling with a fixed non-availability interval. The processing time of a job is a linear increasing function of its starting time, and each job has a release date. A job is either rejected by paying a penalty cost or accepted and processed on the machine. The objective is to minimize the makespan of the accepted jobs and the total rejection penalties of the rejected jobs. We present a fully polynomial-time approximation scheme for the problem. We also show that the special case without non-availability interval can be solved using the same method with a lower order.

previous article A note on area of lattice polygons in an Archimedean tiling

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Cheng, T.C.E., Ding, Q., Lin, B.: A concise survey of scheduling with time-dependent processing times. Eur. J. Oper. Res. 152, 1–13 (2004)CrossRefMATHMathSciNet

Gerstl, E., Mosheiov, G.: Scheduling on parallel identical machines with job-rejection and position-dependent processing times. Inf. Process. Lett. 112, 743–747 (2012)CrossRefMATHMathSciNet

Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979)CrossRefMATHMathSciNet

Hsu, C.J., Chang, C.W.: Unrelated parallel-machine scheduling with deteriorating jobs and rejection. Appl. Mech. Mater. 263–266, 655–659 (2013)

Hsu, C.J., Yang, S.J., Yang, D.L.: Due-date assignment and optional maintenance activity scheduling problem with linear deteriorating jobs. J. Mar. Sci. Technol. 19, 97–100 (2011)

Kononov, A., Gawiejnowicz, S.: NP-hard cases in scheduling deteriorating jobs on dedicated machines. J. Oper. Res. Soc. 52, 708–717 (2001)CrossRefMATH

Kovalyov, M.Y., Kubiak, W.: A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs. J. Heuristics 3, 287–297 (1998)CrossRefMATH

Kovalyov, M.Y., Kubiak, W.: A fully polynomial approximation scheme for the weighted earliness–tardiness problem. Oper. Res. 47, 757–761 (1999)CrossRefMATHMathSciNet

Lee, C.Y.: Machine scheduling with an availability constraint. J. Global. Optim. 9, 363–382 (1996)CrossRef

10.

Li, K., Yang, S.L., Ren, M.L.: Single-machine scheduling problem with resource dependent release dates to minimise total resource-consumption. Int. J. Syst. Sci. 42, 1811–1820 (2011)CrossRefMATHMathSciNet

11.

Li, S.S., Fan, B.Q.: Single-machine scheduling with proportionally deteriorating jobs subject to availability constraints. Asia. Pac. J. Oper. Res. 29(4), (2012). doi:10.1142/S0217595912500194

12.

Li, S.S., Y, J.J.: Parallel-machine scheduling with deteriorating jobs and rejection. Theor. Comput. Sci. 411, 3642–3650 (2010)CrossRefMATH

13.

Li, S.S., Ng, C.T., Cheng, T.C.E., Yuan, J.J.: Parallel-batch scheduling of deteriorating jobs with release dates to minimize the makespan. Eur. J. Oper. Res. 210, 482–488 (2011)CrossRefMATHMathSciNet

14.

Liu, C., Luo, C.X.: Single machine scheduling problem with release dates, rejection and an unavailable interval. J. Chongqing Normal Univ. 30, 17–20 (2013)MATH

15.

Liu, J., Wang, Y., Min, X.: Single-machine scheduling with common due-window assignment for deteriorating jobs. J. Oper. Res. Soc. 65, 291–301 (2014)

16.

Liu, M., Zheng, F.F., Chu, C.B., Xu, Y.F.: Scheduling deteriorating jobs on a single machine with release times and rejection. Discrete Math. Algorithms Appl. (2012). doi:10.1142/S1793830912500322

17.

Luo, C.X.: An FPTAS for uniform parallel-machine scheduling problem with deteriorating jobs and rejection. Appl. Mech. Mater. 433–435, 2335–2338 (2013)CrossRef

18.

Ma, Y., Chu, C.B., Zuo, C.R.: A survey of scheduling with deterministic machine availability constraints. Comput. Ind. Eng. 58, 199–211 (2010)CrossRef

19.

Shabtay, D.: The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost. Eur. J. Oper. Res. 233, 64–74 (2014)CrossRefMathSciNet

20.

Shabtay, D., Gaspar, N., Kaspi, M.: A survey on offline scheduling with rejection. J. Sched. 16, 3–28 (2013)CrossRefMATHMathSciNet

21.

Shen, L.X., Wang, D., Wang, X.Y.: Parallel-machine scheduling with non-simultaneous machine available time. Appl. Math. Model. 37, 5227–5232 (2013)CrossRefMathSciNet

22.

Wang, J.B., Sun, L.H., Sun, L.Y.: Single-machine total completion time scheduling with a time-dependent deterioration. Appl. Math. Model. 35, 1506–1511 (2011)CrossRefMATHMathSciNet

23.

Wang, X.R., Wang, J.J.: Single-machine scheduling with convex resource dependent processing times and deteriorating jobs. Appl. Math. Model. 37, 2388–2393 (2013)CrossRefMathSciNet

24.

Wang, X.Y., Zhou, Z.L., Ji, P., Wang, J.B.: Parallel machines scheduling with simple linear job deterioration and non-simultaneous machine available times. Comput. Ind. Eng. 74, 88–91 (2014)CrossRef

25.

Yuan, J.J., Ng, C.T., Cheng, T.C.E.: Two-agent single-machine scheduling with release dates and preemption to minimize the maximum lateness. J. Sched. (2013). doi:10.1007/s10951-013-0360-y

26.

Zhang, L.Q., Lu, L.F., Yuan, J.J.: Single machine scheduling with release dates and rejection. Eur. J. Oper. Res. 198, 975–978 (2009)CrossRefMATHMathSciNet

27.

Zhang, M.J., Luo, C.X.: Parallel-machine scheduling with deteriorating jobs, rejection and a fixed non-availability interval. Appl. Math. Comput. 224, 405–411 (2013)CrossRefMathSciNet

28.

Zhao, C.L., Tang, H.Y.: Parallel machines scheduling with deteriorating jobs and availability constraints. Jpn. J. Ind. Appl. Math. (2014). doi:10.1007/s13160-014-0150-8

29.

Zhao, C.L., Ji, M., Tang, H.Y.: Parallel-machine scheduling with an availability constraint. Comput. Ind. Eng. 61, 778–781 (2011)CrossRef

30.

Zhao, C.L., Yin, Y.Q., Cheng, T.C.E., Wu, C.C.: Single-machine scheduling and due date assignment with rejection and position-dependent processing times. J. Ind. Manag. Optim. 10, 691–700 (2014)CrossRefMATHMathSciNet

Title: Deteriorating jobs scheduling on a single machine with release dates, rejection and a fixed non-availability interval
Authors: Wei-Xuan Li
Chuan-Li Zhao
Publication date: 01-06-2015
Publisher: Springer Berlin Heidelberg
Published in: Journal of Applied Mathematics and Computing / Issue 1-2/2015
Print ISSN: 1598-5865
Electronic ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-014-0820-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 1-2/2015

Dynamics of an impulsive diffusive ecological model with distributed delay and additive Allee effect

A finite iterative algorithm for Hermitian reflexive and skew-Hermitian solution groups of the general coupled linear matrix equations

A note on area of lattice polygons in an Archimedean tiling

An efficient implementation of a trust region method for box constrained optimization

Analysis of smoothing-type algorithms for the convex second-order cone programming

On the -Ulam–Hyers–Rassias stability of nonautonomous impulsive evolution equations

Premium Partner