nach oben

Journal of Combinatorial Optimization

Erschienen in:

01.01.2021

Research on single-machine scheduling with position-dependent weights and past-sequence-dependent delivery times

verfasst von: Ji-Bo Wang, Bo Cui, Ping Ji, Wei-Wei Liu

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 2/2021

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This article studies scheduling problems with past-sequence-dependent delivery times (denoted by psddt) on a single-machine, i.e., the delivery time of a job depends on its waiting time of processing. We prove that the total (discounted) weighted completion time minimization can be solved in \(O(n\log n)\) time, where n is the number of jobs, and the weight is a position-dependent weight. For common (denoted by con) and slack (denoted by slk) due-date assignment and position-dependent weights (denoted by pdw), we prove that an objective cost minimization is solvable in \(O(n\log n)\) time. The model (i.e., psddt and pdw) can also be extended to position-dependent (time-dependent) processing times.

Vorheriger Artikel Application of multi-objective optimization algorithm for siting and sizing of distributed generations in distribution networks

Nächster Artikel Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination

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

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

Brucker P (2001) Scheduling algorithms, 3rd edn. Springer, BerlinCrossRef

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

Gawiejnowicz S (2008) Time-dependent scheduling. Springer, BerlinCrossRef

Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discret Math 5:287–326MathSciNetCrossRef

Hall NG, Posner ME (1991) Earliness-tardiness scheduling problems, I: weighted deviation of completion times about a common due date. Oper Res 39:836–846MathSciNetCrossRef

Hardy GH, Littlewood JE, Polya G (1967) Inequalities, 2nd edn. Cambridge University Press, CambridgeMATH

Jiang C, Zou D, Bai D, Wang J-B (2020) Proportionate flowshop scheduling with position-dependent weights. Eng Optim 52(1):37–52MathSciNetCrossRef

Kahlbacher H (1992) Termin-und Ablaufplanung-ein analytischer Zugang. Ph.D. thesis, University of Kaiserslautern

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

Li L, Yan P, Ji P, Wang J-B (2018) Scheduling jobs with simultaneous considerations of controllable processing times and learning effect. Neural Comput Appl 29:1155–1162CrossRef

Liu M (2013) Parallel-machine scheduling with past-sequence-dependent delivery times and learning effect. Appl Math Model 37:9630–9633MathSciNetCrossRef

Liu W, Jiang C (2020) Due-date assignment scheduling involving job-dependent learning effects and convex resource allocation. Eng Optim 52(1):74–89MathSciNetCrossRef

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

Liu M, Zheng F, Chu C, Xu Y (2012b) Single-machine scheduling with past-sequence-dependent delivery times and release times. Inf Process Lett 112:835–838MathSciNetCrossRef

Liu M, Wang S, Chu, (2013) Scheduling deteriorating jobs with past-sequence-dependent delivery times. Int J Prod Econ 144:418–421

Liu W, Hu X, Wang X-Y (2017) Single machine scheduling with slack due dates assignment. Eng Optim 49:709–717MathSciNetCrossRef

Lu Y-Y (2016) Research on no-idle permutation flowshop scheduling with time-dependent learning effect and deteriorating jobs. Appl Math Model 40:3447–3450MathSciNetCrossRef

Lu Y-Y, Liu J-Y (2018) A note on resource allocation scheduling with position-dependent workloads. Eng Optim 50:1810–1827MathSciNetCrossRef

Lu Y-Y, Teng F, Feng Z-X (2015) Scheduling jobs with truncated exponential sum-of-logarithm-processing-times based and position-based learning effects. Asia Pac J Oper Res 32:1550026MathSciNetCrossRef

Lu Y-Y, Jin J, Ji P, Wang J-B (2016) Resource-dependent scheduling with deteriorating jobs and learning effects on unrelated parallel machine. Neural Comput Appl 27:1993–2000CrossRef

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

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

Wang J-J, Zhang B-H (2015) Permutation flowshop problems with bi-criterion makespan and total completion time objective and position-weighted learning effects. Comput Oper Res 58:24–31MathSciNetCrossRef

Wang J-B, Ji P, Cheng TCE, Wang D (2012a) Minimizing makespan in a two-machine flow shop with effects of deterioration and learning. Optim Lett 6:1393–1409MathSciNetCrossRef

Wang J-B, Wang M-Z, Ji P (2012b) Single machine total completion time minimization scheduling with a time-dependent learning effect and deteriorating jobs. Int J Syst Sci 43:861–868MathSciNetCrossRef

Wang X-R, Jin J, Wang J-B, Ji P (2014) Single machine scheduling with truncated job-dependent learning effect. Optim Lett 8:669–677MathSciNetCrossRef

Wang J-B, Liu F, Wang J-J (2019) Research on \(m\)-machine flow shop scheduling with truncated learning effects. Int Trans Oper Res 26(3):1135–1151MathSciNetCrossRef

Wang J-B, Gao M, Wang J-J, Liu L, He H (2020) Scheduling with a position-weighted learning effect and job release dates. Eng Optim 52(9):1475–1493MathSciNetCrossRef

Wu Y-B, Wang J-J (2016) Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times. Neural Comput Appl 27:937–943CrossRef

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

Yin Y, Cheng TCE, Xu J, Cheng S-R, Wu C-C (2013) Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. J Ind Manag Optim 9:323–339MathSciNetMATH

Zhao C, Tang H (2014) Single machine scheduling problems with general position-dependent processing times and past-sequence-dependent delivery times. J Appl Math Comput 45:259–274MathSciNetCrossRef

Titel: Research on single-machine scheduling with position-dependent weights and past-sequence-dependent delivery times
verfasst von: Ji-Bo Wang
Bo Cui
Ping Ji
Wei-Wei Liu
Publikationsdatum: 01.01.2021
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 2/2021
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00676-z

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 2/2021

Algorithmic complexity of outer independent Roman domination and outer independent total Roman domination

Bounds on the semipaired domination number of graphs with minimum degree at least two

On sufficient topological indices conditions for properties of graphs

Approximation algorithm for the multicovering problem

Application of multi-objective optimization algorithm for siting and sizing of distributed generations in distribution networks

Zero forcing versus domination in cubic graphs