##
**Order acceptance with weighted tardiness.**
*(English)*
Zbl 1185.90093

Summary: Over the past decade the strategic importance of order acceptance has been widely recognized in practice as well as academic research. This paper examines order acceptance decisions when capacity is limited, customers receive a discount for late delivery, but early delivery is neither penalized nor rewarded. We model a manufacturing facility that considers a pool of orders, and chooses for processing the subset that results in the highest profit. We present several solution methods, beginning with a straightforward application of an approach which separates sequencing and job acceptance. We then develop an optimal branch-and-bound procedure that uses a linear (integer) relaxation for bounding and performs the sequencing and job acceptance decisions jointly. We develop a variety of fast and high-quality heuristics based on this approach. For small problems, beam search runs almost 20 times faster than the benchmark, with a high degree of accuracy, and a branch-and-bound heuristic using Vogel’s method for bounding is over 100 times faster with very high accuracy. For larger problems, a myopic heuristic based on the relaxation runs 2000 times faster than the beam-search benchmark, with comparable accuracy.

### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C59 | Approximation methods and heuristics in mathematical programming |

### Software:

IMSL Numerical Libraries
PDFBibTeX
XMLCite

\textit{S. A. Slotnick} and \textit{T. E. Morton}, Comput. Oper. Res. 34, No. 10, 3029--3042 (2007; Zbl 1185.90093)

Full Text:
DOI

### References:

[1] | Hill, T., Manufacturing strategy (2000), Irwin McGraw-Hill: Irwin McGraw-Hill New York |

[2] | Guerrero, H. H.; Kern, G. M., How to more effectively accept and refuse orders, Production and Inventory Management, 29, 4, 59-63 (1988) |

[3] | Shapiro BP, Moriarty RT, Cline CE. Fabtek(A). Boston, MA, 1992.; Shapiro BP, Moriarty RT, Cline CE. Fabtek(A). Boston, MA, 1992. |

[4] | Slotnick, S. A.; Morton, T. E., Selecting jobs for a heavily loaded shop with lateness penalties, Computers and Operations Research, 23, 2, 131-140 (1996) · Zbl 0871.90050 |

[5] | Lewis, H. F.; Slotnick, S. A., Multi-period job selection: planning work loads to maximize profit, Computers and Operations Research, 28, 1, 1081-1098 (2002) · Zbl 0995.90050 |

[6] | Balakrishnan, N.; Patterson, J. W.; Sridharan, V., Rationing capacity between two product classes, Decision Sciences, 27, 2, 185-214 (1996) |

[7] | Harris, F. H.; Pinder, J. P., A revenue management approach to demand management and order booking in assemble-to-order manufacturing, Journal of Operations Management, 13, 299-309 (1995) |

[8] | Slotnick, S. A.; Sobel, M. J., Manufacturing lead-time rules: customer retention vs. tardiness costs, European Journal of Operational Research, 163, 3, 825-856 (2005) · Zbl 1071.90540 |

[9] | Chatterjee, S.; Slotnick, S. A.; Sobel, M. J., Delivery guarantees and the interdependence of marketing and operations, Production and Operations Management, 11, 3, 393-410 (2002) |

[10] | Gordon, V.; Proth, J.; Chu, C., A survey of the state-of-the-art of common due-date assignment and scheduling research, European Journal of Operational Research, 139, 1-25 (2001) · Zbl 1009.90054 |

[11] | Ghosh, J. B., Job selection in a heavily loaded shop, Computers and Operations Research, 24, 2, 141-145 (1997) · Zbl 0893.90089 |

[12] | Alidaee, B.; Kochenberger, G. A.; Amini, M. M., Greedy solutions of selection and ordering problems, European Journal of Operational Research, 134, 203-215 (2001) · Zbl 0990.90565 |

[13] | Gietzmann, M. B.; Monahan, G., Absorption versus direct costing: the relevance of opportunity costs in the management of congested stochastic production systems, Management Accounting Research, 7, 409-429 (1996) |

[14] | Weng, Z. K., Strategies for integrating lead time and customer-order decisions, IIE Transactions, 31, 2, 161-171 (1999) |

[15] | Guerrero, H. H.; Kern, G. M., A conceptual model for demand management in the assemble-to-order environment, Journal of Operations Management, 9, 1, 65-83 (1990) |

[16] | Wu, M. C.; Chen, S. Y., A cost model for justifying the acceptance of rush orders, International Journal of Production Research, 34, 1963-1974 (1996) · Zbl 0928.90039 |

[17] | Wu, M. C.; Chen, S. Y., A multiple criteria decision-making model for justifying the acceptance of rush orders, Production Planning and Control, 8, 753-761 (1997) |

[18] | Roundy, R.; Chen, C.; 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, IIIE Transactions, 37, 12, 1093-1105 (2005) |

[19] | Wester, F. A.W.; Wijngaard, J.; Zijm, W. H.M., Order acceptance strategies in a production-to-order environment with setup times and due-dates, International Journal of Production Research, 30, 1313-1326 (1992) · Zbl 0825.90541 |

[20] | Charnsirisakskul, K.; Griffin, P. M.; Keskinocak, P., Order selection and scheduling with leadtime flexibility, IIE Transactions, 36, 697-707 (2004) |

[21] | Charnsirisakskul, K.; Griffin, P. M.; Keskinocak, P., Pricing and scheduling with leadtime flexibility, European Journal of Operational Research, 171, 1, 153-169 (2006) · Zbl 1091.90016 |

[22] | Yang B, Geunes J. Heuristic approaches for solving single resource scheduling problems with job-selection flexibility. Technical Report, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL; 2004.; Yang B, Geunes J. Heuristic approaches for solving single resource scheduling problems with job-selection flexibility. Technical Report, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL; 2004. |

[23] | De, P.; Ghosh, J. B.; Wells, C. E., Job selection and sequencing on a single machine in a random environment, European Journal of Operational Research, 70, 425-431 (1993) · Zbl 0782.90049 |

[24] | Balakrishnan, N.; Patterson, J. W.; Sridharan, V., An experimental comparison of capacity rationing models, International Journal of Production Research, 35, 6, 1639-1649 (1997) · Zbl 0943.90574 |

[25] | Balakrishnan, N.; Patterson, J. W.; Sridharan, V., Robustness of capacity rationing policies, European Journal of Operational Research, 115, 328-338 (1999) · Zbl 0938.90018 |

[26] | ten Kate, H. A., Towards a better understanding of order acceptance, International Journal of Production Economics, 37, 139-152 (1994) |

[27] | ten Kate HA. Order acceptance and production control. PhD thesis, University of Groningen, 1995.; ten Kate HA. Order acceptance and production control. PhD thesis, University of Groningen, 1995. |

[28] | Ebben, M. J.R.; Hans, E. W.; Olde Weghuis, F. M., Workload based order acceptance in job shop environments, OR Spectrum, 27, 107-122 (2005) · Zbl 1176.90207 |

[29] | Kingsman, B. G., Modelling input-output workload control for dynamic capacity planning in production planning systems, International Journal of Production Economics, 68, 73-93 (2000) |

[30] | Raaymakers, W. H.M.; Bertrand, JW. M.; Fransoo, J. C., The performance of workload rules for order acceptance in batch chemical manufacturing, Journal of Intelligent Manufacturing, 11, 217-228 (2000) |

[31] | Raaymakers, W. H.M.; Bertrand, J. W.M.; Fransoo, J. C., Using aggregate estimation models for order acceptance in a decentralized production control structure for batch chemical engineering, IIE Transactions, 32, 989-998 (2000) |

[32] | Ivanescu, C. V.; Fransoo, J. C.; Bertrand, J. W.M., Makespan estimation and order acceptance in batch process industries when processing times are uncertain, OR Spectrum, 24, 467-495 (2002) · Zbl 1028.90518 |

[33] | Du, J.; Leung, J. Y.-T., Minimizing total tardiness on one machine is NP-hard, Mathematics of Operations Research, 15, 483-495 (1990) · Zbl 0714.90052 |

[34] | Ow, P. S.; Morton, T. E., Filtered beam search in scheduling, International Journal of Production Research, 26, 1, 35-62 (1988) |

[35] | Ow, P. S.; Morton, T. E., The single machine early/tardy problem, Management Science, 35, 2, 177-191 (1989) · Zbl 0666.90043 |

[36] | Valente, J. M.S.; Alves, R. A.F. S., Filtered and recovering beam search for the early/tardy scheduling problem with no idle time, Computers and Industrial Engineering, 48, 363-375 (2005) · Zbl 1095.90046 |

[37] | Charalambous, O.; Hindi, K., KBSS: a knowledge-based job-shop scheduling system, Production Planning and Control, 4, 4, 304-310 (1993) |

[38] | Sabuncuoglu, I.; Bayizi, M., Job shop scheduling with beam search, European Journal of Operational Research, 118, 390-412 (1999) · Zbl 0940.90037 |

[39] | Framinan, J. M.; Ruiz-Usano, R., On transforming job-shops into flow-shops, Production Planning and Control, 13, 2, 166-174 (2002) |

[40] | Neumann, K.; Schwindt, C., Project scheduling with inventory constraints, Mathematical Models of Operations Research, 56, 513-533 (2002) · Zbl 1064.90018 |

[41] | Matanachai, S.; Yano, C. A., Balanced mixed-model assembly lines to reduce work overload, IIE Transactions, 33, 29-42 (2001) |

[42] | Erel, E.; Sabuncuoglu, I.; Sekerci, H., Stochastic assembly line balancing using beam search, International Journal of Production Research, 43, 7, 1411-1426 (2005) · Zbl 1068.90045 |

[43] | Nair, S. K.; Thakur, L. S.; Wen, K.-W., Near optimal solutions for product line design and selection: beam search heuristics, Management Science, 41, 5, 767-785 (1995) · Zbl 0843.90055 |

[44] | Alexouda, G.; Paparrizos, K., A genetic algorithm approach to the product line design problem using the seller’s return criterion: an extensive comparative computational study, European Journal of Operational Research, 134, 165-178 (2001) · Zbl 0990.90580 |

[45] | Alexouda, G., An evolutionary algorithm approach to the share of choices problem in product line design, Computers and Operations Research, 31, 2215-2229 (2004) · Zbl 1068.68141 |

[46] | Morton TE, Rachamadagu RM. Myopic heuristics for the single machine weighted tardiness problem. Working Paper No. 30-82-83, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA; 1982.; Morton TE, Rachamadagu RM. Myopic heuristics for the single machine weighted tardiness problem. Working Paper No. 30-82-83, Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA; 1982. |

[47] | Morton, T. E.; Pentico, D. W., Heuristic scheduling systems: with applications to production engineering and project management (1993), Wiley: Wiley New York |

[48] | Montagne, E. R., Sequencing with time delay costs, Industrial Engineering Research Bulletin, 5 (1969) |

[49] | IMSL. User’s manual: FORTRAN subroutines for statistical analysis. 1991 [chapter 18: Random number generation].; IMSL. User’s manual: FORTRAN subroutines for statistical analysis. 1991 [chapter 18: Random number generation]. |

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.