Top

Journal of Combinatorial Optimization

Published in:

01-01-2014

Competitive analysis for make-to-order scheduling with reliable lead time quotation

Authors: Feifeng Zheng, E. Zhang, Yinfeng Xu, Wei-Chiang Hong

Published in: Journal of Combinatorial Optimization | Issue 1/2014

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

search-config

AI-assisted search

Off

Abstract

This paper makes extended studies on the discrete problem of online scheduling and reliable lead time quotation (discrete Q-SLTQ) introduced by Keskinocak et al. (Manag. Sci. 47(2):264–279, 2001). We first relax the assumption on revenue function from a linear decreasing function to any decreasing function. We present an online deterministic strategy which is optimal in competitiveness for concave revenue functions. The above results are further extended to the continuous Q-SLTQ model where orders are released at arbitrary time points. For the discrete Q-SLTQ problem, if orders are with nonuniform lengths, we prove the nonexistence of online strategies with bounded competitive ratios; otherwise if orders are with unit length but various weights, we present an optimal online strategy.

previous article Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width

next article Spanning 3-connected index of graphs

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

Ata B, Olsen TL (2009) Near-optimal dynamic lead-time quotation and scheduling under convex-concave customer delay costs. Oper Res 57(3):753–768 CrossRefMATH

Borodin A, El-Yaniv R (1998) Online computation and competitive analysis. Cambridge University Press, Cambridge, pp 2–5 (Chapter 1) MATH

Chang P, Hieh J, Liao TW (2005) Evolving fuzzy rules for due date assignment problem in semiconductor manufacturing factory. J Intell Manuf 16(4–5):549–557 CrossRef

Duenyas I, Hopp WJ (1995) Quoting customer lead times. Manag Sci 41:43–57 CrossRefMATH

Eilon S, Chowdhury IG (1976) Due dates in job shop scheduling. Int J Prod Res 14(2):223–237 CrossRef

Fung SPY (2010) Online preemptive scheduling with immediate decision or notification and penalties. In: 16th annual international computing and combinatorics conference, Nha Trang, Vietnam, pp 389–398

Goldwasser MH, Kerbikov B (2003) Admission control with immediate notification. J Sched 6(3):269–285 CrossRefMATHMathSciNet

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

Handfield RB, Nichols EL (1999) Introduction to supply chain management. Prentice Hall, New York

Hsu SY, Sha DY (2004) Due date assignment using artificial neural networks under different shop floor control strategies. Int J Prod Res 42(9):1727–1745 CrossRefMATH

Kaminsky P, Hochbaum D (2004) Due date quotation models and algorithms. In: Leung JY (ed) Handbook on scheduling algorithms, methods and models. Chapman Hall/CRC, London

Kaminsky P, Lee ZH (2008) Effective on-line algorithms for reliable due date quotation and large-scale scheduling. J Sched 11(3):187–204 CrossRefMATHMathSciNet

Keskinocak P, Ravi R, Tayur S (2001) Scheduling and reliable lead-time quotation for orders with availability intervals and lead-time sensitive revenues. Manag Sci 47(2):264–279 CrossRefMATH

Portougal V, Trietsch D (2006) Setting due dates in a stochastic single machine environment. Comput Oper Res 33(6):1681–1694 CrossRefMATH

Savasaneril S, Griffin PM, Keskinocak P (2010) Dynamic lead-time quotation for an M/M/1 base-stock inventory queue. Oper Res 58(2):383–395 CrossRefMATHMathSciNet

Slotnick SA, Sobel MJ (2005) Manufacturing lead-time rule: customer retention versus tardiness costs. Eur J Oper Res 163(3):825–856 CrossRefMATH

Title: Competitive analysis for make-to-order scheduling with reliable lead time quotation
Authors: Feifeng Zheng
E. Zhang
Yinfeng Xu
Wei-Chiang Hong
Publication date: 01-01-2014
Publisher: Springer US
Published in: Journal of Combinatorial Optimization / Issue 1/2014
Print ISSN: 1382-6905
Electronic ISSN: 1573-2886
DOI: https://doi.org/10.1007/s10878-012-9502-y

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/2014

Radiation hybrid map construction problem parameterized

On certain geometric properties of the Yao–Yao graphs

The edge-centered surface area of the arrangement graph

Distance- independent set problems for bipartite and chordal graphs

Reconfiguration graphs for vertex colourings of chordal and chordal bipartite graphs

Preface

Premium Partner