zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
A branch and bound algorithm for single machine scheduling with deteriorating values of jobs. (English) Zbl 1201.90087
Summary: Scheduling deteriorating jobs is an area of research which has attracted much attention recently. In this paper the problem of single machine scheduling, where the values of jobs remaining after processing deteriorate over time, is presented. A branch and bound method is developed, which, using the sub-optimal solution of a heuristic algorithm as an initial solution, leads to the optimal solution of the problem. The method is applied in a case of remanufacturing of PCs and is evaluated by comparing the results (in terms of computer time needed for the application) to those of complete enumeration.

90B35Scheduling theory, deterministic
90C57Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI
[1] Browne, S.; Yechiali, U.: Scheduling deteriorating jobs on a single processor, Operations research 38, No. 3, 495-498 (1990) · Zbl 0703.90051 · doi:10.1287/opre.38.3.495
[2] Gupta, J. N. D.; Gupta, S. K.: Single facility scheduling with nonlinear processing times, Computers and industrial engineering 14, No. 4, 387-393 (1988)
[3] Hsu, Y. S.; Lin, B. M. T.: Minimization of maximum lateness under linear deterioration, Omega 31, 459-469 (2003)
[4] Mosheiov, G.: Scheduling jobs under simple linear deterioration, Computers and operations research 21, No. 6, 653-659 (1994) · Zbl 0810.90074 · doi:10.1016/0305-0548(94)90080-9
[5] Alidaee, B.; Womer, N. K.: Scheduling with time dependent processing times: review and extensions, Journal of the operational research society 50, 711-720 (1999) · Zbl 1054.90542
[6] Cheng, T. C. E.; Ding, Q.; Lin, B. M. T.: A concise survey of scheduling with time-dependent processing times, European journal of operational research 152, 1-13 (2004) · Zbl 1030.90023 · doi:10.1016/S0377-2217(02)00909-8
[7] Bachman, A.; Janiak, A.; Kovalyov, M. Y.: Minimizing the total weighted completion time of deteriorating jobs, Information processing letters 81, No. 2, 81-84 (2002) · Zbl 1032.68019 · doi:10.1016/S0020-0190(01)00196-X
[8] Bachman, A.; Cheng, E. T. C.; Janiak, A.; Ng, C. T.: Scheduling start time dependent jobs to minimize the total weighted completion time, Journal of the operational research society 53, No. 6, 688-693 (2002) · Zbl 1059.90063 · doi:10.1057/palgrave.jors.2601359
[9] Cheng, E. T. C.; Ding, Q.; Kovalyov, M. Y.; Bachman, A.; Janiak, A.: Scheduling jobs with piecewise linear decreasing processing times, Naval research logistics 50, No. 6, 531-534 (2003) · Zbl 1043.90027 · doi:10.1002/nav.10073
[10] Inderfurth, K.; Janiak, A.; Kovalyov, M. Y.; Werner, F.: Batching work and rework processes with limited deterioration of reworkables, Computers operations research 33, No. 6, 1595-1605 (2006) · Zbl 1087.90008 · doi:10.1016/j.cor.2004.11.009
[11] Inderfurth, K.; Kovalyov, M. Y.; Ng, C. T.; Werner, F.: Cost minimizing scheduling of work and rework processes on a single facility under deterioration of reworkables, International journal of production economics 105, No. 2, 345-356 (2007)
[12] Janiak, A.; Kovalyov, M. Y.: Job sequencing with exponential functions of processing times, Informatica 17, No. 1, 13-24 (2006) · Zbl 1178.68102
[13] Ng, C. T.; Cheng, E. T. C.; Bachman, A.; Janiak, A.: Three scheduling problems with deteriorating jobs to minimize the total completion time, Information processing letters 81, No. 6, 327-333 (2002) · Zbl 1059.90063
[14] Voutsinas, T. G.; Pappis, C. P.: Scheduling jobs with values exponentially deteriorating over time, International journal of production economics 79, 163-169 (2002)
[15] Janiak, A.; Krysiak, T.: Single processor scheduling with job values depending on their completion times, Journal of scheduling 10, No. 2, 129-138 (2007) · Zbl 1154.90462 · doi:10.1007/s10951-006-0004-6
[16] A. Janiak, T. Krysiak, C.P. Pappis, T.G. Voutsinas, A scheduling problem with job values exponentially dependent on their completion times, in: Proceedings of the 10th International Workshop on Project Management and Scheduling, Poznan, Poland, April 26--28, 2006, pp. 180--186 · Zbl 1151.90015
[17] A. Janiak, T. Krysiak, C.P. Pappis, Parallel processor scheduling problems with exponential models of job values, Scheduling in computer and manufacturing systems, Warszawa, 2006, pp. 115--134
[18] A. Janiak, T. Krysiak, Scheduling of the jobs with stepwise values on the parallel unrelated processors, in: Proceedings of the 16th International Conference on Systems Science, Wroclaw, Poland, September 4--6, 2007, pp. 87--94
[19] De Ron, Ad; Penev, K.: Disassembly and recycling of electronic consumer products: an overview, Technovation 15, No. 6, 363-374 (1995)
[20] Nixdorf Siemens, Computer reuse and recycling: Learning by experience at Siemens Nixdorf, Siemens Nixdorf Informationssysteme AG, Paderborn/Munich, Internal Report, 1997
[21] Ferrer, G.: The economics of personal computer remanufacturing, Resources, conservation and recycling 21, 79-108 (1997)
[22] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. Rinnooy: Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of discrete mathematics 3, 287-326 (1979) · Zbl 0411.90044
[23] Janiak, A.; Krysiak, T.; Pappis, C. P.; Voutsinas, T. G.: A scheduling problem with job values given as a power function of their completion times, European journal of operational research 193, 836-848 (2009) · Zbl 1151.90015 · doi:10.1016/j.ejor.2007.11.006