nach oben

Journal of Combinatorial Optimization

Erschienen in:

16.09.2020

Minimizing maximum delivery completion time for order scheduling with rejection

verfasst von: Ren-Xia Chen, Shi-Sheng Li

Erschienen in: Journal of Combinatorial Optimization | Ausgabe 4/2020

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

We study an order scheduling problem with rejection, in which each order consists of multiple product types and each product type should be manufactured on a dedicated machine. The aim is to find a solution to minimize a linear sum of the maximum delivery completion time of the accepted orders and the total penalty of the rejected orders. Even if the delivery times of all orders are zero, the problem is shown to be binary \(\mathcal{NP}\)-hard in the two-machine case and it is shown to be unary \(\mathcal{NP}\)-hard when the number of machines is arbitrary. Three approximation algorithms are proposed and their worst-case performance ratios are analyzed. For the scenario where the number of machines is fixed, a pseudo-polynomial dynamic programming algorithm and a fully polynomial time approximation scheme are devised for it.

Vorheriger Artikel A linear time algorithm for the p-maxian problem on trees with distance constraint

Nächster Artikel An approximation algorithm for submodular hitting set problem with linear penalties

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

Ahmadi R, Bagchi U (1990) Scheduling of multi-job customer orders in multi-machine environments. ORSA/TIMS, Philadelphia

Ahmadi R, Bagchi U, Roemer TA (2005) Coordinated scheduling of customer orders for quick response. Naval Res Logist 52:493–512MathSciNetMATH

Bartal Y, Leonardi S, Spaccamela AM, Sgall J, Stougie L (2000) Multiprocessor scheduling with rejection. SIAM J Discrete Math 13:64–78MathSciNetMATH

Carlier J (1982) The one-machine sequencing problem. Eur J Oper Res 11:42–47MathSciNetMATH

Cesaret B, Oǧuz C, Salman FS (2012) A tabu search algorithm for order acceptance and scheduling. Comput Oper Res 39:1197–1205

Chen YJ, Lu LF, Yuan JJ (2015) Preemptive scheduling on identical machines with delivery coordination to minimize the maximum delivery completion time. Theoret Comput Sci 583:67–77MathSciNetMATH

Garey MR, Johnson DS (1979) Computers and Intractablity: a guide to the theory of \(\cal{NP}\)-completeness. Freeman, San Francisco

Framinan JM, Perez-Gonzalez P (2017) New approximate algorithms for the customer order scheduling problem with total completion time objective. Comput Oper Res 78:181–192MathSciNetMATH

Framinan JM, Perez-Gonzalez P (2018) Order scheduling with tardiness objective: improved approximate solutions. Eur J Oper Res 266:840–850MathSciNetMATH

Framinan JM, Perez-Gonzalez P, Fernandez-Viagas V (2019) Deterministic assembly scheduling problems: a review and classification of concurrent-type scheduling models and solution procedures. Eur J Oper Res 273:401–417MathSciNetMATH

Geramipour S, Moslehi G, Reisi-Nafchi M (2017) Maximizing the profit in customer’s order acceptance and scheduling problem with weighted tardiness penalty. J Oper Res Soc 68:89–101

Ghosh JB (1997) Job selection in a heavily loaded shop. Comput Oper Res 24:141–145MATH

He C, Leung JYT, Lee K, Pinedo ML (2016) Improved algorithms for single machine scheduling with release dates and rejections. 4OR 14:41–55MathSciNetMATH

He L, Guijt A, Weerdt M, Xing L, Yorke-Smith N (2019) Order acceptance and scheduling with sequence-dependent setup times: a new memetic algorithm and benchmark of the state of the art. Comput Ind Eng 138:106102

Julien FM, Magazine MJ (1990) Scheduling customer orders: an alternative production scheduling approach. J Manuf Opera Manag 3:177–199

Kacem I, Kellerer H (2018) Approximation schemes for minimizing the maximum lateness on a single machine with release times under non-availability or deadline constraints. Algorithmica 80:3825–3843MathSciNetMATH

Kacem I, Kellerer H, Seifaddini M (2016) Efficient approximation schemes for the maximum lateness minimization on a single machine with a fixed operator or machine non-availability interval. J Comb Optim 32:970–981MathSciNetMATH

Karmarkar N (1984) A new polynomial-time algorithm for linear programming. In: Proceedings of the sixteenth annual ACM symposium on theory of computing (STOC), pp 302–311

Kung JY, Duan J, Xu J, Chung IH, Cheng SR, Wu CC, Lin WC (2018) Metaheuristics for order scheduling problem with unequal ready times. Discrete Dyn Nat Soc article ID: 4657368

Lann A, Mosheiov G, Rinott Y (1998) Asymptotic optimality in probability of a heuristic schedule for open shops with job overlaps. Oper Res Lett 22:63–68MathSciNetMATH

Lee IS (2013) Minimizing total tardiness for the order scheduling problem. Int J Prod Econ 144:128–134

Leung JYT, Li H, Pinedo ML (2005) Order scheduling in an environment with dedicated resources in parallel. J Sched 8:355–386MathSciNetMATH

Leung JYT, Li H, Pinedo ML (2006a) Approximation algorithms for minimizing total weighted completion time of orders on identical machines in parallel. Naval Res Logist 53:243–260MathSciNetMATH

Leung JYT, Li H, Pinedo ML (2006b) Scheduling orders for multiple product types with due date related objectives. Eur J Oper Res 168:370–389MathSciNetMATH

Leung JYT, Li H, Pinedo ML (2007) Scheduling orders for multiple product types to minimize total weighted completion time. Discrete Appl Math 155:945–970MathSciNetMATH

Leung JYT, Li H, Pinedo ML (2008) Scheduling orders on either dedicated or flexible machines in parallel to minimize total weighted completion time. Ann Oper Res 159:107–123MathSciNetMATH

Lin BMT, Kononov AV (2007) Customer order scheduling to minimize the number of late jobs. Eur J Oper Res 183:944–948MATH

Lin WC, Xu J, Bai D, Chung IH, Liu SC, Wu CC (2019) Artificial bee colony algorithms for the order scheduling with release dates. Soft Comput 23:8677–8688

Lin WC, Yin Y, Cheng SR, Cheng TCE, Wu CH, Wu CC (2017) Particle swarm optimization and opposite-based particle swarm optimization for two-agent multi-facility customer order scheduling with ready times. Appl Soft Comput 52:877–884

Lu LF, Zhang LQ (2017) Single-machine scheduling with production and rejection costs to minimize the maximum earliness. J Comb Optim 34:331–342MathSciNetMATH

Mastrolilli M, Queyranne M, Schulz AS, Svensson O, Uhane NA (2010) Minimizing the sum of weighted completion times in a concurrent open shop. Oper Res Lett 38:390–395MathSciNetMATH

Naderi B, Roshanaei V (2020) Branch-relax-and-check: a tractable decomposition method for order acceptance and identical parallel machine scheduling. Eur J Oper Res 286:811–827MathSciNetMATH

Nobibon FT, Leus R (2011) Exact algorithms for a generalization of the order acceptance and scheduling problem in a single machine environment. Comput Oper Res 38:367–378MathSciNetMATH

Ng CT, Cheng TCE, Yuan JJ (2003) Concurrent open shop scheduling to minimize the weighted number of tardy jobs. J Sched 6:405–412MathSciNetMATH

Ou J, Zhong X, Wang G (2015) An improved heuristic for parallel machine scheduling with rejection. Eur J Oper Res 241:653–661MathSciNetMATH

Potts CN (1980) Analysis of a heuristic for one machine sequencing with release dates and delivery times. Oper Res 28:1436–1441MathSciNetMATH

Riahi V, Newton MAH, Polash MMA, Sattar A (2019) Tailoring customer order scheduling search algorithms. Comput Oper Res 108:155–165MathSciNetMATH

Rom WO, Slotnick SA (2009) Order acceptance using genetic algorithms. Comput Oper Res 36:1758–1767MATH

Sengupta S (2003) Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection. Lect Notes Comput Sci 2748:79–90MathSciNetMATH

Shabtay D, Gasper N, Kaspi M (2013) A survey on scheduling problems with rejection. J Sched 16:3–28MathSciNetMATH

Shi Z, Huang Z, Shi L (2018) Customer order scheduling on batch processing machines with incompatible job families. Int J Prod Res 56:795–808

Shi Z, Wang L, Liu P, Shi L (2017) Minimizing completion time for order scheduling: formulation and heuristic algorithm. IEEE Trans Autom Sci Eng 14:1558–1569

Slotnick SA (2011) Order acceptance and scheduling: a taxonomy and review. Eur J Oper Res 212:1–11MathSciNet

Slotnick SA, Morton TE (2007) Order acceptance with weighted tardiness. Comput Oper Res 34:3029–3042

Slotnick SA, Morton TE (1996) Selecting jobs for a heavily loaded shop with lateness penalties. Comput Oper Res 23:131–140MATH

Sung CS, Yoon SH (1998) Minimizing total weighted completion time at a pre-assembly stage composed of two feeding machines. Int J Prod Econ 54:247–255

Wagneur E, Sriskandarajah C (1993) Open shops with jobs overlap. Eur J Oper Res 71:366–378MATH

Wang G, Cheng TCE (2007) Customer order scheduling to minimize total weighted completion time. Omega 35:623–626

Wang X, Huang G, Hu X, Cheng TCE (2015) Order acceptance and scheduling on two identical parallel machines. J Oper Res Soc 66:1755–1767

Wang S, Ye B (2019) Exact methods for order acceptance and scheduling on unrelated parallel machines. Comput Oper Res 104:159–173MathSciNetMATH

Wu CC, Lin WC, Zhang X, Chung IH, Yang TH, Lai K (2019a) Tardiness minimization for a customer order scheduling problem with sum-of-processing-time-based learning effect. J Oper Res Soc 70:487–501

Wu CC, Yang TH, Zhang X, Kang CC, Lin WC (2019b) Using heuristic and iterative greedy algorithms for the total weighted completion time order scheduling with release times. Swarm Evol Comput 44:913–926

Wu CC, Liu SC, Lin TY, Yang TH, Chung IH, Lin WC (2018a) Bicriterion total flowtime and maximum tardiness minimization for an order scheduling problem. Comput Ind Eng 117:152–163

Wu GH, Cheng CY, Yang HI, Chena CT (2018b) An improved water flowlike algorithm for order acceptance and scheduling with identical parallel machines. Appl Soft Comput 71:1072–1084

Xu J, Wu CC, Yin Y, Zhao C, Chiou YT, Lin WC (2016) An order scheduling problem with position-based learning effect. Comput Oper Res 74:175–186MathSciNetMATH

Xu X, Ma Y, Zhou Z, Zhao Y (2015) Customer order scheduling on unrelated parallel machines to minimize total completion time. IEEE Trans Autom Sci Eng 12:244–257

Yang J (2005) The complexity of customer order scheduling problems on parallel machines. Comput Oper Res 32:1921–1939MathSciNetMATH

Zhang LQ, Lu LF (2016) Parallel-machine scheduling with release dates and rejection. 4OR 14:165–172MathSciNetMATH

Zhang LQ, Lu LF, Yuan JJ (2009) Single machine scheduling with release dates and rejection. Eur J Oper Res 198:975–978MathSciNetMATH

Zhang X, Xu D, Du D, Wu C (2018) Approximation algorithms for precedence-constrained identical machine scheduling with rejection. J Comb Optim 35:318–330MathSciNetMATH

Zhang Y, Dan Y, Dan B, Gao H (2019) The order scheduling problem of product-service system with time windows. Comput Ind Eng 133:253–266

Zhong X, Ou J (2017) Improved approximation algorithms for parallel machine scheduling with release dates and job rejection. 15:387–406

Zhong X, Pan Z, Jiang D (2017) Scheduling with release times and rejection on two parallel machines. J Comb Optim 33:934–944MathSciNetMATH

Titel: Minimizing maximum delivery completion time for order scheduling with rejection
verfasst von: Ren-Xia Chen
Shi-Sheng Li
Publikationsdatum: 16.09.2020
Verlag: Springer US
Erschienen in: Journal of Combinatorial Optimization / Ausgabe 4/2020
Print ISSN: 1382-6905
Elektronische ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-020-00649-2

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 4/2020

The maximum Wiener index of maximal planar graphs

A linear time algorithm for the p-maxian problem on trees with distance constraint

Maximizing user type diversity for task assignment in crowdsourcing

Connected max cut is polynomial for graphs without the excluded minor

General multiplicative Zagreb indices of trees and unicyclic graphs with given matching number

An approximation algorithm for submodular hitting set problem with linear penalties