×

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.

MSC:

90B35 Deterministic scheduling theory in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Browne, S.; Yechiali, U., Scheduling deteriorating jobs on a single processor, Operations Research, 38, 3, 495-498 (1990) · Zbl 0703.90051
[2] Gupta, J. N.D.; Gupta, S. K., Single facility scheduling with nonlinear processing times, Computers and Industrial Engineering, 14, 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, 6, 653-659 (1994) · Zbl 0810.90074
[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
[7] Bachman, A.; Janiak, A.; Kovalyov, M. Y., Minimizing the total weighted completion time of deteriorating jobs, Information Processing Letters, 81, 2, 81-84 (2002) · Zbl 1032.68019
[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, 6, 688-693 (2002) · Zbl 1059.90063
[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, 6, 531-534 (2003) · Zbl 1043.90027
[10] Inderfurth, K.; Janiak, A.; Kovalyov, M. Y.; Werner, F., Batching work and rework processes with limited deterioration of reworkables, Computers & Operations Research, 33, 6, 1595-1605 (2006) · Zbl 1087.90008
[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, 2, 345-356 (2007)
[12] Janiak, A.; Kovalyov, M. Y., Job sequencing with exponential functions of processing times, Informatica, 17, 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, 6, 327-333 (2002)
[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, 2, 129-138 (2007) · Zbl 1154.90462
[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; 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; 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; 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, 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; 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.; Rinnooy Kan, A. H.G., 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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.