Order Acceptance Using Genetic Algorithms

摘要

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. The 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.