nach oben

Soft Computing

Erschienen in:

26.10.2015 | Methodologies and Application

A two-agent single-machine scheduling problem with late work criteria

verfasst von: Du-Juan Wang, Chao-Chung Kang, Yau-Ren Shiau, Chin-Chia Wu, Peng-Hsiang Hsu

Erschienen in: Soft Computing | Ausgabe 8/2017

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

This paper addresses a two-agent scheduling problem where the objective is to minimize the total late work of the first agent, with the restriction that the maximum lateness of the second agent cannot exceed a given value. Two pseudo-polynomial dynamic programming algorithms are presented to find the optimal solutions for small-scale problem instances. For medium- to large-scale problem instances, a branch-and-bound algorithm incorporating the implementation of a lower bounding procedure, some dominance rules and a Tabu Search-based solution initialization, is developed to yield the optimal solution. Computational experiments are designed to examine the efficiency of the proposed algorithms and the impacts of all the relative parameters.

Vorheriger Artikel A semantics-based approach to multi-source heterogeneous information fusion in the internet of things

Nächster Artikel Flexible neural trees based early stage identification for IP traffic

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

Agnetis A, Mirchandani PB, Pacciarelli D, Pacifici A (2004) Scheduling problems with two competing agents. Oper Res 52:229–242MathSciNetCrossRefMATH

Agnetis A, Pascale G, Pacciarelli D (2009) A Lagrangian approach to single-machine scheduling problems with two competing agents. J Sched 12:401–415MathSciNetCrossRefMATH

Baker KR, Smith JC (2003) A multiple criterion model for machine scheduling. J Sched 6:7–16MathSciNetCrossRefMATH

Blazewicz J (1984) Scheduling preemptible tasks on parallel processors with information loss. Tech Sci Inform 3(6):415–420MathSciNetMATH

Blazewicz J, Pesch E, Sterna M, Werner F (1999) Total late work criteria for shop scheduling problems. In: Inderfurth K, Schwödiauer G, Domschke W, Juhnke F, Kleinschmidt P, Waescher G (eds) Operations research proceedings. Springer, Berlin, pp 354–359

Blazewicz J, Pesch E, Sterna M, Werner F (2004) Open shop scheduling problems with late work criteria. Discret Appl Math 134:1–24MathSciNetCrossRefMATH

Cheng TCE, Cheng SR, Wu WH, Hsu PH, Wu CC (2011) A two-agent single-machine scheduling problem with truncated sum-of-processing-times-based learning considerations. Comput Ind Eng 60:534–541CrossRef

Gerstl E, Mosheiov G (2012) Scheduling problems with two competing agents to minimize weighted earliness-tardiness. Comput Oper Res 40:109–116CrossRefMATH

Guo P, Cheng W, Wang Y (2014) A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. J Ind Manag Optim 10(4):1071–1090MathSciNetCrossRefMATH

Glover F (1977) Heuristics for integer programming using surrogate constraints. Decis Sci 8(1):156–166CrossRef

Glover F (1989) Tabu search—part I. INFORMS J Comput 1(3):190–206MathSciNetCrossRefMATH

Hall NG, Posner ME (2001) Generating experimental data for computation testing with machine scheduling applications. Oper Res 8:54–865MATH

Ke H, Ma J (2014) Modeling project time-cost trade-off in fuzzy random environment. Appl Soft Comput 19:80–85CrossRef

Lee WC, Chen SK, Chen WC, Wu CC (2011) A two-machine flowshop problem with two agents. Comput Oper Res 38:98–104MathSciNetCrossRefMATH

Lee K, Choi BC, Leung JYT, Pinedo ML (2009) Approximation algorithms for multi-agent scheduling to minimize total weighted completion time. Inf Process Lett 109:913–917MathSciNetCrossRefMATH

Leung JYT, Pinedo M, Wan G (2010) Competitive two-agent scheduling and its applications. Oper Res 58:458–469MathSciNetCrossRefMATH

Li S, Yuan J (2012) Unbounded parallel-batching scheduling with two competitive agents. J Sched 15:629–640MathSciNetCrossRefMATH

Liao LM, Huang CJ (2011) Tabu search heuristic for two-machine flowshop with batch processing machines. Comput Ind Eng 60:426–432CrossRef

Lin BMT, Hsu SW (2005) Minimizing total late work on a single machine with release and due dates, In: SIAM conference on computational science and engineering, Orlando

Liu P, Yi N, Zhou XY (2011) Two-agent single-machine scheduling problems under increasing linear deterioration. Appl Math Model 35:2290–2296MathSciNetCrossRefMATH

Li J, Pan Q, Wang F (2014) A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem. Appl Soft Comput 24:63–77CrossRef

Li G, Lu X (2015) Two-machine scheduling with periodic availability constraints to minimize makespan. J Ind Manag Optim 11(2):685–700MathSciNetCrossRefMATH

Mor B, Mosheiov G (2010) Scheduling problems with two competing agents to minimize minmax and minsum earliness measures. Eur J Oper Res 206:540–546MathSciNetCrossRefMATH

Mor B, Mosheiov G (2011) Single machine batch scheduling with two competing agents to minimize total flowtime. Eur J Oper Res 215:524–531MathSciNetCrossRefMATH

Ng CT, Cheng TCE, Yuan JJ (2006) A note on the complexity of the two-agent scheduling on a single machine. J Comb Optim 12:387–394MathSciNetCrossRefMATH

Potts CN, Van Wassenhove LN (1991a) Single machine scheduling to minimize total late work. Oper Res 40:586–595

Potts CN, Van Wassenhove LN (1991b) Approximation algorithms for scheduling a single machine to minimize total late work. Oper Res Lett 11:261–266

Pei J, Pardalos PM, Liu X, Fan W, Yang S, Wang L (2015) Coordination of production and transportation in supply chain scheduling. J Ind Manag Optim 11(2):399–419MathSciNetMATH

Ren J, Zhang Y, Sun G (2009) The NP-hardness of minimizing the total late work on an unbounded batch machine. Asia-Pac J Oper Res 26(3):351–363MathSciNetCrossRefMATH

Roy PK, Bhui S, Paul C (2014) Solution of economic load dispatch using hybrid chemical reaction optimization approach. Appl Soft Comput 24:109–125CrossRef

Sterna M (2007) Dominance relations for two-machine flow shop problem with late work criterion. Bull Pol Acad Sci 55:59–69MATH

Sterna M (2011) A survey of scheduling problems with late work criteria. Omega 39:120–129CrossRef

Tuong NH, Soukhal A, Billaut JC (2012) Single-machine multi-agent scheduling problems with a global objective function. J Sched 15:311–332MathSciNetCrossRefMATH

Wan G, Vakati RS, Leung JYT, Pinedo M (2010) Scheduling two agents with controllable processing times. Eur J Oper Res 205:528–539MathSciNetCrossRefMATH

Wu W-H, Yin Y, Wu W-H, Wu C-C, Hsu P-H (2014) A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. J Ind Manag Optim 10(2):591–611MathSciNetCrossRefMATH

Yin Y, Cheng SR, Cheng TCE, Wu CC, Wu WH (2012a) Two-agent single-machine scheduling with assignable due dates. Appl Math Comput 219:1674–1685

Yin Y, Cheng SR, Cheng TCE, Wu WH, Wu CC (2013a) Two-agent single-machine scheduling with release times and deadlines. Int J Shipp Transp Logist 5:75–94

Yin Y, Cheng SR, Wu CC (2012b) Scheduling problems with two agents and a linear non-increasing deterioration to minimize earliness penalties. Inf Sci 189:282–292

Yin Y, Wu C-C, Wu W-H, Hsu C-J, Wu W-H (2013b) A branch-and-bound procedure for a single-machine earliness scheduling problem with two agents. Appl Soft Comput 13(2):1042–1054

Yuan X, Ji B, Zhang S, Tian H, Hou Y (2014) A new approach for unit commitment problem via binary gravitational search algorithm. Appl Soft Comput 22:249–260CrossRef

Zhao K, Lu X (2013) Approximation schemes for two-agent scheduling on parallel machines. Theor Comput Sci 468:114–121MathSciNetCrossRefMATH

Zhao CL, Yin Y, Cheng TCE, Wu C-C (2014) Single-machine scheduling and due date assignment with rejection and position-dependent processing times. J Ind Manag Optim 10(3):691–700MathSciNetCrossRefMATH

Titel: A two-agent single-machine scheduling problem with late work criteria
verfasst von: Du-Juan Wang
Chao-Chung Kang
Yau-Ren Shiau
Chin-Chia Wu
Peng-Hsiang Hsu
Publikationsdatum: 26.10.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 8/2017
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-015-1900-5

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 8/2017

Channel Status based Sliding Contention Window (CS-SCW) algorithm: A Fuzzy Control Approach for Medium Access in Wireless Networks

A SOM-based Chan–Vese model for unsupervised image segmentation

Multi-view spectral clustering via robust local subspace learning

Enabling public auditability for operation behaviors in cloud storage

A position-aware Merkle tree for dynamic cloud data integrity verification

A novel semi-supervised learning method for Internet application identification