×

Exact algorithms for a generalization of the order acceptance and scheduling problem in a single-machine environment. (English) Zbl 1231.90220

Summary: This paper studies a generalization of the order acceptance and scheduling problem in a single-machine environment where a pool consisting of firm planned orders as well as potential orders is available from which an over-demanded company can select. The capacity available for processing the accepted orders is limited and each order is characterized by a known processing time, delivery date, revenue and a weight representing a penalty per unit-time delay beyond the delivery date. We prove that the existence of a constant-factor approximation algorithm for this problem is unlikely. We propose two linear formulations that are solved using an IP solver and we devise two exact branch-and-bound procedures able to solve instances with up to 50 jobs within reasonable CPU times. We compare the efficiency and quality of the results obtained using the different solution approaches.

MSC:

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

References:

[1] Ahuja, R. K.; Magnanti, T. L.; Orlin, J. B., Network flows: theory, algorithms, and applications (1993), Prentice-Hall, Inc: Prentice-Hall, Inc New Jersey · Zbl 1201.90001
[2] Alidaee, B.; Kochenberger, G.; Amini, M., Greedy solutions of selection and ordering problems, European Journal of Operational Research, 134, 203-215 (2001) · Zbl 0990.90565
[3] Bigras, L.-P.; Gamache, M.; Savard, G., Time-indexed formulations and the total weighted tardiness problem, INFORMS Journal on Computing, 20, 133-142 (2008) · Zbl 1243.90057
[4] Cesaret B, Oguz C, Salman FS. A tabu search algorithm for order acceptance and scheduling. In: T’Kindt V, editor. Proceedings of the 12th international conference on project management and scheduling. Tours, France, April 26-28 2010. p. 141-4.; Cesaret B, Oguz C, Salman FS. A tabu search algorithm for order acceptance and scheduling. In: T’Kindt V, editor. Proceedings of the 12th international conference on project management and scheduling. Tours, France, April 26-28 2010. p. 141-4.
[5] Chuzhoy J, Ostrovsky R, Rabani Y. Approximation algorithms for the job interval selection problem and related scheduling problems. In: IEEE symposium on foundations of computer science, 2001. p. \(348-56 \langle\) citeseer.ist.psu.edu/chuzhoy01approximation.html \(\rangle \); Chuzhoy J, Ostrovsky R, Rabani Y. Approximation algorithms for the job interval selection problem and related scheduling problems. In: IEEE symposium on foundations of computer science, 2001. p. \(348-56 \langle\) citeseer.ist.psu.edu/chuzhoy01approximation.html \(\rangle \) · Zbl 1278.90146
[6] De, P.; Ghosh, J. B.; Wells, C. E., On the minimization of the weighted number of tardy jobs with random processing times and deadline, Computers & Operations Research, 18, 5, 457-463 (1991) · Zbl 0744.90040
[7] Emmons, H., One machine sequencing to minimize certain functions of job tardiness, Operations Research, 17, 701-715 (1969) · Zbl 0176.50005
[8] Engels, D. W.; Karger, D. R.; Kolliopoulos, S. G.; Sengupta, S.; Uma, R. N.; Wein, J., Techniques for scheduling with rejection, Journal of Algorithms, 49, 175-191 (2003) · Zbl 1067.68024
[9] Epstein, L.; Nogab, J.; Woeginger, G. J., On-line scheduling of unit time jobs with rejection: minimizing the total completion time, Operations Research Letters, 30, 415-420 (2002) · Zbl 1013.90063
[10] Ghosh, J. B., Job selection in a heavily loaded shop, Computers & Operations Research, 24, 2, 141 (1997) · Zbl 0893.90089
[11] Goldberg, A. V.; Kennedy, R., An efficient cost scaling algorithm for the assignment problem, Mathematical Programming, 71, 153-177 (1995) · Zbl 0846.90118
[12] Guerrero, H. H.; Kern, G. M., How to more effectively accept and refuse orders, Production and Inventory Management Journal, 4, 59-62 (1998)
[13] Gupta, S. K.; Kyparisis, J.; Ip, C.-M., Project selection and sequencing to maximize net present value of the total return, Management Science, 38, 751-752 (1992) · Zbl 0825.90547
[14] Herbots, J.; Herroelen, W.; Leus, R., Dynamic order acceptance and capacity planning on a single bottleneck resource, Naval Research Logistics, 54, 8, 874-889 (2007) · Zbl 1135.90307
[15] Ivănescu, V. C.; Fransoo, J. C.; Bertrand, J. W., A hybrid policy for order acceptance in batch process industries, OR Spectrum, 28, 199-222 (2006) · Zbl 1101.90031
[16] Keskinocak, P.; Tayur, S., Due date management policies, (Simchi-Levi, D.; Wu, S. D.; Shen, Z. J., Handbook of quantitative supply chain analysis: modeling in the e-business era (2004), Kluwer), 485-547, [Chapter 12] · Zbl 1105.90313
[17] Kleywegt, A. J.; Papastavrou, J. D., The dynamic and stochastic knapsack problem with random sized items, Operations Research, 49, 1, 26-41 (2001) · Zbl 1163.90714
[18] Lawler, E. L., A “pseudopolynomial” algorithm for sequencing jobs to minimize total tardiness, Annals of Discrete Mathematics, 1, 331-342 (1977) · Zbl 0353.68071
[19] Lenstra, J. K.; Rinnooy Kan, A. H.; Brucker, P., Complexity of machine scheduling problems, Annals of Discrete Mathematics, 1, 343-362 (1977) · Zbl 0353.68067
[20] Lewis, H. F.; Slotnick, S. A., Multi-period job selection: planning work loads to maximize profit, Computers & Operations Research, 29, 1081-1098 (2002) · Zbl 0995.90050
[21] Lu, L.; Zhang, L.; Yuan, J., The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan, Theoretical Computer Science, 396, 283-289 (2008) · Zbl 1145.68007
[22] Meng-Gérard, J.; Chrétienne, P.; Baptiste, P.; Sourd, F., On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups, Discrete Applied Mathematics, 157, 3656-3664 (2009) · Zbl 1185.90087
[23] Oguz, C.; Salman, F. S.; Yalcin, Z. B., Order acceptance and scheduling decisions in make-to-order systems, International Journal of Production Economics, 125, 200-211 (2010)
[24] Pan, Y.; Shi, L., On the equivalence of the max-min transportation lower bound and the time-indexed lower bound for single-machine scheduling problems, Mathematical Programming, Series A, 110, 543-559 (2007) · Zbl 1205.90133
[25] Potts, C. N.; Van Wassenhove, L. N., A branch and bound algorithm for the total weighted tardiness problem, Operations Research, 33, 2, 363-377 (1985) · Zbl 0566.90046
[26] Rinnooy Kan, A. H.G.; Lageweg, B. J.; Lenstra, J. K., Minimizing total cost in one-machine scheduling, Operations Research, 23, 908-927 (1975) · Zbl 0324.90039
[27] Rom, W. O.; Slotnick, S. A., Order acceptance using genetic algorithms, Computers & Operations Research, 36, 6, 1758-1767 (2009) · Zbl 1179.90151
[28] Roundy, R.; Chen, D.; Chen, P.; Cakanyildirim, M.; Freimer, M. B.; Melkonian, V., Capacity-driven acceptance of customer orders for a multi-stage batch manufacturing system: models and algorithms, IIE Transactions, 37, 1093-1105 (2005)
[29] Sengupta S. Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection. In: Lecture notes in computer science, vol. 2748. 2003. p. 79-90.; Sengupta S. Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection. In: Lecture notes in computer science, vol. 2748. 2003. p. 79-90. · Zbl 1278.90172
[30] Slotnick, S. A.; Morton, T. E., Selecting jobs for a heavily loaded shop with lateness penalties, Computers & Operations Research, 23, 131-140 (1996) · Zbl 0871.90050
[31] Slotnick, S. A.; Morton, T. E., Order acceptance with weighted tardiness, Computers & Operations Research, 34, 10, 3029-3042 (2007) · Zbl 1185.90093
[32] Talla Nobibon F, Herbots J, Leus R. Order acceptance and scheduling in a single-machine environment: exact and heuristic algorithms. Working paper KBI-0903, K.U. Leuven, 2009.; Talla Nobibon F, Herbots J, Leus R. Order acceptance and scheduling in a single-machine environment: exact and heuristic algorithms. Working paper KBI-0903, K.U. Leuven, 2009.
[33] Tanaka, S.; Fujikuma, S.; Araki, M., An exact algorithm for single-machine scheduling without machine idle time, Journal of Scheduling, 12, 575-593 (2009) · Zbl 1182.90051
[34] Van Den Akker, J. M.; Hurkens, C. A.J.; Savelsbergh, M. W.P., Time-indexed formulations for single-machine scheduling problems: column generation, INFORMS Journal on Computing, 12, 111-124 (2000) · Zbl 1034.90004
[35] Yang, B.; Geunes, J., A single resource scheduling problem with job-selection flexibility, tardiness costs and controllable processing times, Computers & Industrial Engineering, 53, 420-432 (2007)
[36] Yugma, C., Dynamic management of a portfolio of orders, 4OR: A Quarterly Journal of Operations Research, 3, 167-170 (2005) · Zbl 1134.90479
[37] Zijm, W. H.M., Towards intelligent manufacturing planning and control systems, OR Spektrum, 22, 313-345 (2000) · Zbl 0973.90030
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.