A hybrid genetic and linear programming algorithm for two-agent order acceptance and scheduling problem

In this paper, the simultaneous order acceptance and scheduling problem is developed by considering the variety of customers' requests. To that end, two agents with different scheduling criteria including the total weighted lateness for the first and the weighted number of tardy orders for the second agent are considered. The objective is to maximize the sum of the total profit of the first and the total revenue of the second agents' orders when the weighted number of tardy orders of the second agent is bounded by an upper bound value. In this study, it is shown that this problem is NP-hard in the strong sense, and then to optimally solve it, an integer linear programming model is proposed based on the properties of optimal solution. This model is capable of solving problem instances up to 60 orders in size. Also, the LP-relaxation of this model was used to propose a hybrid meta-heuristic algorithm which was developed by employing genetic algorithm and linear programming. Computational results reveal that the proposed meta-heuristic can achieve near optimal solutions so efficiently that for the instances up to 60 orders in size, the average deviation of the model from the optimal solution is lower than 0.2% and for the instances up to 150 orders in size, the average deviation from the problem upper bound is lower than 1.5%. (C) 2015 Elsevier B.V. All rights reserved.