##
**Order acceptance using genetic algorithms.**
*(English)*
Zbl 1179.90151

Summary: This paper uses a genetic algorithm to solve the order-acceptance problem with tardiness penalties. We compare the performance of a myopic heuristic and a genetic algorithm, both of which do job acceptance and sequencing, using an upper bound based on an assignment relaxation. We conduct a pilot study, in which we determine the best settings for diversity operators (clone removal, mutation, immigration, population size) in connection with different types of local search. Using a probabilistic local search provides results that are almost as good as exhaustive local search, with much shorter processing times. Our main computational study shows that the genetic algorithm always dominates the myopic heuristic in terms of objective function, at the cost of increased processing time. We expect that our results will provide insights for the future application of genetic algorithms to scheduling problems.Scope and purposeThe importance of the order-acceptance decision has gained increasing attention over the past decade. This decision is complicated by the trade-off between the benefits of the revenue associated with an order, on one hand, and the costs of capacity, as well as potential tardiness penalties, on the other. In this paper, we use a genetic algorithm to solve the problem of which orders to choose to maximize profit, when there is limited capacity and an order delivered after its due date incurs a tardiness penalty. The genetic algorithm improves upon the performance of previous methods for large problems.

### MSC:

90B35 | Deterministic scheduling theory in operations research |

90C59 | Approximation methods and heuristics in mathematical programming |

68T99 | Artificial intelligence |

### Software:

IMSL Numerical Libraries
PDFBibTeX
XMLCite

\textit{W. O. Rom} and \textit{S. A. Slotnick}, Comput. Oper. Res. 36, No. 6, 1758--1767 (2009; Zbl 1179.90151)

### References:

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

[2] | 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 |

[3] | 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 |

[4] | Slotnick, S. A.; Morton, T. E., Order acceptance with weighted tardiness, Computers and Operations Research, 34, 3029-3042 (2007) · Zbl 1185.90093 |

[5] | Keskinocak, P.; Tayur, S., Due date management policies, (Handbook of quantitative supply chain analysis: modeling in the E-business era (2004), Kluwer: Kluwer Boston, MA), 485-556 · Zbl 1105.90313 |

[6] | 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, 12, 1093-1105 (2005) |

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

[8] | 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 |

[9] | 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 |

[10] | Gietzmann, M.; 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) |

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

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

[13] | 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 |

[14] | 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) |

[15] | Kolisch, R., Integrated production planning, order acceptance, and due date setting for make-to-order manufacturing, (Operations research proceedings (1998), Springer: Springer New York, NY), 492-497 |

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

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

[18] | Wester, F.; Wijngaard, J.; Zijm, W., 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 |

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

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

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

[22] | Ono, K.; Jones, C., An heuristic approach to acceptance rules in integrated scheduling systems, Journal of Operations Research Society of Japan, 16, 1, 37-58 (1973) |

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

[24] | ten Kate HA. Order acceptance and production control. Ph.D. thesis, University of Groningen; 1995.; ten Kate HA. Order acceptance and production control. Ph.D. thesis, University of Groningen; 1995. |

[25] | Wouters, M., Relevant cost information for order acceptance decisions, Production Planning and Control, 8, 1, 2-9 (1997) |

[26] | Verdaasdonk, P.; Wouters, M., Defining an information structure to analyse resource spending changes of operations management decisions, Production Planning and Control, 10, 2, 162-174 (1999) |

[27] | Wang, J.; Yang, J. Q.; Lee, H., Multicriteria order acceptance decision support in over-demanded job shops: a neural network approach, Mathematical Computer Modelling, 19, 5, 1-19 (1994) · Zbl 0809.68096 |

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

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

[30] | Raaymakers, W. H.M.; Bertrand, J. 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) |

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

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

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

[34] | Yang B, Geunes J. Heuristic approaches for solving single resource scheduling problems with job-selection flexibility. Technical Report, Working Paper, 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, Working Paper, Department of Industrial and Systems Engineering, University of Florida, Gainesville, FL; 2004. |

[35] | Ko, H.; Evans, G., A genetic-algorithm based heuristic for the dynamic integrated forward/reverse logistics network for 3PLs, Computers and Operations Research, 34, 346-366 (2007) · Zbl 1113.90028 |

[36] | Alvarenga, G.; Mateus, G.; de Tomi, G., A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows, Computers and Operations Research, 34, 1561-1584 (2007) · Zbl 1163.90357 |

[37] | Elaoud, S.; Teghem, J.; Baouaziz, B., Genetic algorithms to solve the cover printing problem, Computers and Operations Research, 34, 3346-3361 (2007) · Zbl 1163.90728 |

[38] | Bautista, J.; Pereira, J., Modeling the problem of locating collection areas for urban waste management. An application to the metropolitan area of Barcelona, Omega, 34, 617-629 (2006) |

[39] | Norman, B. A.; Smith, A. E., Continuous approach to considering uncertainty in facility design, Computers and Operations Research, 33, 6, 1760-1775 (2006) · Zbl 1087.90089 |

[40] | Tyni, T.; Ylinen, J., Evolutionary bi-objective optimisation in the elevator car routing problem, European Journal of Operational Research, 169, 3, 960-977 (2006) · Zbl 1079.90511 |

[41] | Vroblefski, M.; Brown, E. C., A grouping genetic algorithm for registration area planning, Omega, 34, 3, 220-230 (2006) |

[42] | Zhang, G. Q.; Lai, K. K., Combining path relinking and genetic algorithms for the multiple-level warehouse layout problem, European Journal of Operational Research, 169, 2, 413-425 (2006) · Zbl 1079.90016 |

[43] | 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 |

[44] | 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 |

[45] | Moz, M.; Pato, M. V., A genetic algorithm approach to the nurse rerostering problem, Computers and Operations Research, 34, 667-691 (2007) · Zbl 1120.90330 |

[46] | Cheng, Y. H.; Shih, C., Maximizing the cooling capacity and COP of two-stage thermoelectric coolers through genetic algorithm, Applied Thermal Engineering, 26, 8/9, 937-947 (2006) |

[47] | Jiao, J.; Zhang, Y.; Wang, Y., A heuristic genetic algorithm for product portfolio planning, Computers and Operations Research, 34, 1777-1799 (2007) · Zbl 1159.90371 |

[48] | Lensberg, T.; Eilifsen, A.; McKee, T. E., Bankruptcy theory development and classification via genetic programming, European Journal of Operational Research, 169, 2, 677-697 (2006) · Zbl 1181.91114 |

[49] | Avci, S.; Akturk, M. S.; Storer, R., A problem space algorithm for single machine weighted tardiness problems, IIE Transactions, 35, 479-486 (2003) |

[50] | Mattfeld, D.; Bierwirth, C., An efficient genetic algorithm for job shop scheduling with tardiness objectives, European Journal of Operational Research, 155, 616-630 (2004) · Zbl 1044.90035 |

[51] | Sevaux, M.; Dauzère-Pérès, S., Genetic algorithms to minimize the weighted number of late jobs on a single machine, European Journal of Operational Research, 151, 296-306 (2003) · Zbl 1053.90046 |

[52] | Bolat, A.; Al-Harkan, I.; Al Harbi, B., Flow-shop scheduling for three serial stations with the last two duplicate, Computers and Operations Research, 32, 647-667 (2005) · Zbl 1061.90044 |

[53] | Etiler, O.; Toklu, B.; Atak, M.; Wilson, J., A genetic algorithm for flow shop scheduling problems, Journal of the Operational Research Society, 55, 830-835 (2004) · Zbl 1060.90035 |

[54] | Franca, P.; Gupta, J.; Mendes, A.; Moscato, P.; Veltink, K., Evolutionary algorithms for scheduling a flowshop manufacturing cell with sequence dependent family setups, Computers and Industrial Engineering, 48, 491-506 (2005) |

[55] | Ruiz, R.; Maroto, C.; Alcarez, J., Solving the flowshop scheduling problem with sequence dependent setup times using advanced metaheuristics, European Journal of Operational Research, 165, 34-54 (2005) · Zbl 1112.90338 |

[56] | Chiu, N. C.; Fang, S. C.; Lee, Y. S., Sequencing parallel machining operations by genetic algorithms, Computers and Industrial Engineering, 36, 259-280 (1999) |

[57] | Koh, S. G.; Koo, P. H.; Ha, J. W.; Lee, W. S., Scheduling parallel batch processing machines with arbitrary job sizes and incompatible job families, International Journal of Production Research, 42, 19, 4091-4107 (2004) · Zbl 1060.90643 |

[58] | Jou, C., A genetic algorithm with sub-indexed partitioning genes and its application to production scheduling of parallel machines, Computers and Industrial Engineering, 48, 39-54 (2005) |

[59] | Kurz, M.; Askin, R., Scheduling flexible flow lines with sequence-dependent setup times, European Journal of Operational Research, 159, 66-82 (2004) · Zbl 1067.90045 |

[60] | Lee, S. M.; Asllani, A. A., Job scheduling with dual criteria and sequence-dependent setups: mathematical versus genetic programming, Omega, 45, 32, 145-153 (2004) |

[61] | Hino, C. M.; Ronconi, D. P.; Mendes, A. B., Minimizing earliness and tardiness penalties in a single-machine problem with a common due date, European Journal of Operational Research, 160, 190-201 (2005) · Zbl 1067.90043 |

[62] | M’Hallah, R., Minimizing total earliness and tardiness on a single machine using a hybrid heuristic, Computers and Operations Research, 34, 3126-3142 (2007) · Zbl 1185.90088 |

[63] | Ghedjati, F., Genetic algorithms for the job-shop scheduling problem with unrelated parallel constraints: heuristic mixing method machines and precedence, Computers and Industrial Engineering, 37, 39-42 (1999) |

[64] | Prins, C., Competitive genetic algorithms for the open-shop scheduling problem, Mathematical Methods of Operations Research, 52, 389-411 (2000) · Zbl 1023.90030 |

[65] | Ponnambalam, S. G.; Aravindan, P.; Rao, P. S., Comparative evaluation of genetic algorithms for job-shop scheduling, Production Planning and Control, 12, 6, 560-574 (2001) |

[66] | Park, B. J.; Choi, H. R.; Kim, H. S., A hybrid genetic algorithm for the job shop scheduling problems, Computers and Industrial Engineering, 45, 597-613 (2003) |

[67] | Cavory, G.; Dupas, R.; Goncalves, G., A genetic approach to solving the problem of cyclic job shop scheduling with linear constraints, European Journal of Operations Research, 161, 73-85 (2005) · Zbl 1065.90034 |

[68] | Bean, J. C., Genetic algorithms and random keys for sequencing and optimization, ORSA Journal on Computing, 6, 154-160 (1994) · Zbl 0807.90060 |

[69] | Cheng, R.; Gen, M.; Tsujimura, Y., A tutorial survey of job-shop scheduling problems using genetic algorithms—I. Representation, Computers and Industrial Engineering, 30, 983-997 (1996) |

[70] | Cheng, R.; Gen, M.; Tsujimura, Y., A tutorial survey of job-shop scheduling problems using genetic algorithms—II. Hybrid genetic search strategies, Computers and Industrial Engineering, 36, 343-364 (1999) |

[71] | Ruiz, R.; Maroto, C., A comprehensive review and evaluation of permutation flowshop heuristics, European Journal of Operational Research, 165, 479-494 (2005) · Zbl 1066.90038 |

[72] | Essafi, I.; Mati, Y.; Dauzère-Pérès, S., A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem, Computers and Operations Research, 35, 2599-2616 (2008) · Zbl 1177.90155 |

[73] | Malve, S.; Uzsoy, R., A genetic algorithm for minimizing maximum lateness on parallel identical batch processing machines with dynamic job arrivals and incompatible job families, Computers and Operations Research, 34, 3016-3028 (2007) · Zbl 1185.90086 |

[74] | Morton TE, Rachamadugu 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, Rachamadugu 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. |

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

[76] | Goldberg, D. E., Genetic algorithms in search, optimization and machine learning (1989), Addison-Wesley: Addison-Wesley Reading, MA · Zbl 0721.68056 |

[77] | Cheng, R.; Gen, M.; Tsujimura, Y., A tutorial survey of job-shop scheduling problems using genetic algorithms—part II. Hybrid genetic search strategies, Computers and Industrial Engineering, 37, 51-55 (1999) |

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

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.