nach oben

Journal of Applied Mathematics and Computing

Erschienen in:

01.06.2014 | Original Research

Single machine scheduling problems with general position-dependent processing times and past-sequence-dependent delivery times

verfasst von: Chuanli Zhao, Hengyong Tang

Erschienen in: Journal of Applied Mathematics and Computing | Ausgabe 1-2/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

This paper considers single machine scheduling with past-sequence-dependent (psd) delivery times, in which the processing time of a job depends on its position in a sequence. We provide a unified model for solving single machine scheduling problems with psd delivery times. We first show how this unified model can be useful in solving scheduling problems with due date assignment considerations. We analyze the problem with four different due date assignment methods, the objective function includes costs for earliness, tardiness and due date assignment. We then consider scheduling problems which do not involve due date assignment decisions. The objective function is to minimize makespan, total completion time and total absolute variation in completion times. We show that each of the problems can be reduced to a special case of our unified model and solved in O(n ³) time. In addition, we also show that each of the problems can be solved in O(nlogn) time for the spacial case with job-independent positional function.

Vorheriger Artikel An impulsive periodic predator-prey Lotka–Volterra type dispersal system with mixed functional responses

Nächster Artikel Dynamics of n+1-dimensional impulsive reaction-diffusion predator-prey system with Holling type III functional response

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Adamopoulos, G.I., Pappis, C.P.: Single machine scheduling with flow allowances. J. Oper. Res. Soc. 47, 1280–1285 (1996) CrossRefMATH

Bachman, A., Janiak, A.: Scheduling jobs with position-dependent processing times. J. Oper. Res. Soc. 55, 257–264 (2004) CrossRefMATH

Biskup, D.: Single-machine scheduling with learning considerations. Eur. J. Oper. Res. 115, 173–178 (1999) CrossRefMATH

Biskup, D.: A state-of-the-art review on scheduling with learning effects. Eur. J. Oper. Res. 188, 315–329 (2008) CrossRefMATHMathSciNet

Cheng, T.C.E., Wu, C.C., Lee, W.C.: Some scheduling problems with sum-of-processing-times-based and job-position-based learning effects. Inf. Sci. 178, 2476–2487 (2008) CrossRefMATHMathSciNet

Cheng, T.C.E., Wu, C.C., Lee, W.C.: Some scheduling problems with deteriorating jobs and learning effects. Comput. Ind. Eng. 54, 972–982 (2008) CrossRef

Cheng, T.C.E., Lee, W.C., Wu, C.C.: Scheduling problems with deteriorating jobs and learning effects including proportional setup times. Comput. Ind. Eng. 58, 326–331 (2010) CrossRef

Cheng, T.C.E., Lee, W.C., Wu, C.C.: Single-machine scheduling with deteriorating jobs and past-sequence-dependent setup times. Appl. Math. Model. 35, 1861–1867 (2011) CrossRefMATHMathSciNet

Cheng, T.C.E., Wu, C.C., Chen, J.C., Wu, W.H., Cheng, S.R.: Two-machine flowshop scheduling with a truncated learning function to minimize the makespan. Int. J. Prod. Econ. 141, 79–86 (2013) CrossRef

10.

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

11.

Janiak, A., Rudek, R.: Scheduling jobs under an aging effect. J. Oper. Res. Soc. 60, 1–8 (2009)

12.

Kanet, J.J.: Minimizing variation of flow time in a single machine systems. Manag. Sci. 27, 1453–1459 (1981) CrossRefMATH

13.

Kim, B.L., Ozturkoglu, Y.: Scheduling a single machine with multiple preventive maintenance activities and position-based deteriorations using genetic algorithms. Int. J. Adv. Manuf. Technol. 67, 1127–1137 (2013) CrossRef

14.

Koulamas, C., Kyparisis, G.J.: Single-machine scheduling problems with past-sequence-dependent delivery times. Int. J. Prod. Econ. 126, 264–266 (2010) CrossRef

15.

Kuo, W.H., Yang, D.L.: Minimizing the makespan in a single-machine scheduling problem with the cyclic process of an aging effect. J. Oper. Res. Soc. 59, 416–420 (2008) CrossRefMATH

16.

Lee, W.C., Wu, C.C., Sung, H.J.: A bi-criterion single-machine scheduling problem with learning considerations. Acta Inform. 40, 303–315 (2004) CrossRefMATHMathSciNet

17.

Liman, S.D., Panwalkar, S.S., Thongmee, S.: Common due window size and location determination in a single machine scheduling problem. J. Oper. Res. Soc. 49, 1007–1010 (1998) CrossRefMATH

18.

Liu, M., Zheng, F.F., Chu, C.B., Xu, Y.F.: New results on single-machine scheduling with past-sequence-dependent delivery times. Theor. Comput. Sci. 438, 55–61 (2012) CrossRefMATHMathSciNet

19.

Mosheiov, G.: Scheduling problems with a learning effect. Eur. J. Oper. Res. 132, 687–693 (2001) CrossRefMATHMathSciNet

20.

Mosheiov, G.: Parallel machine scheduling with a learning effect. J. Oper. Res. Soc. 52, 1165–1169 (2001) CrossRefMATH

21.

Mosheiov, G., Sidney, J.B.: Scheduling with general job-dependent learning curves. Eur. J. Oper. Res. 147, 665–670 (2003) CrossRefMATHMathSciNet

22.

Mosheiov, G.: A note on scheduling deteriorating jobs. Math. Comput. Model. 41, 883–886 (2005) CrossRefMATHMathSciNet

23.

Mosheiov, G.: Proportionate flowshops with general position-dependent processing times. Inf. Process. Lett. 111, 174–177 (2011) CrossRefMATHMathSciNet

24.

Ozturkoglu, Y., Bulfin, R.L.: A unique integer mathematical model for scheduling deteriorating jobs with rate-modifying-activities on a single machine. Int. J. Adv. Manuf. Technol. 57, 753–762 (2011) CrossRef

25.

Panwalkar, S.S., Smith, M.L., Seidmann, A.: Common due date assignment to minimize total penalty for the one machine scheduling problem. Oper. Res. 30, 391–399 (1982) CrossRefMATH

26.

Rustogi, K., Strusevich, V.A.: Simple matching vs. linear assignment in scheduling models with positional effects: a critical review. Eur. J. Oper. Res. 222, 393–407 (2012) CrossRefMATHMathSciNet

27.

Seidmann, A., Panwalkar, S.S., Smith, M.L.: Optimal assignment of due dates for a single processor scheduling problem. Int. J. Prod. Res. 19, 393–399 (1981) CrossRef

28.

Wu, C.C., Lee, W.C., Chen, T.: Heuristic algorithms for solving the maximum lateness scheduling problem with learning considerations. Comput. Ind. Eng. 52, 124–132 (2007) CrossRef

29.

Wu, C.C., Lee, W.C.: Single-machine and flowshop scheduling with a general learning effect model. Comput. Ind. Eng. 56, 1553–1558 (2009) CrossRef

30.

Wu, C.C., Hsu, P.H., Chen, J.C., Wang, N.S.: Genetic algorithm for minimizing the total weighted completion time scheduling problem with learning and release times. Comput. Oper. Res. 38, 1025–1034 (2011) CrossRefMATHMathSciNet

31.

Yang, D.L., Cheng, T.C.E., Kuo, W.H.: Scheduling with a general learning effect. Int. J. Adv. Manuf. Technol. 67, 217–229 (2013) CrossRef

32.

Yang, S.J., Yang, D.L.: Single-machine scheduling problems with past-sequence-dependent delivery times and position-dependent processing times. J. Oper. Res. Soc. 63, 1508–1515 (2012) CrossRef

33.

Zhao, C.L., Tang, H.Y.: Single machine scheduling with general job-dependent aging effect and maintenance activities to minimize makespan. Appl. Math. Model. 34, 837–841 (2010) CrossRefMATHMathSciNet

Titel: Single machine scheduling problems with general position-dependent processing times and past-sequence-dependent delivery times
verfasst von: Chuanli Zhao
Hengyong Tang
Publikationsdatum: 01.06.2014
Verlag: Springer Berlin Heidelberg
Erschienen in: Journal of Applied Mathematics and Computing / Ausgabe 1-2/2014
Print ISSN: 1598-5865
Elektronische ISSN: 1865-2085
DOI: https://doi.org/10.1007/s12190-013-0722-9

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1-2/2014

Exponential type vector variational-like inequalities and vector optimization problems with exponential type invexities

Extremal inverse eigenvalue problem for symmetric doubly arrow matrices

Solvability of fractional order differential systems with general nonlocal conditions

Positive solutions for a high-order semipositone fractional differential equation with integral boundary conditions

Dynamics of a stochastic Lotka-Volterra model with regime switching

On the entropy of LEGO ®

Premium Partner