Order acceptance and scheduling on two identical parallel machines

Abstract

We study the order acceptance and scheduling problem on two identical parallel machines. At the beginning of the planning horizon, a firm receives a set of customer orders, each of which has a revenue value, processing time, due date, and tardiness weight. The firm needs to select orders to accept and schedule the accepted orders on two identical parallel machines so as to maximize the total profit. The problem is intractable, so we develop two heuristics and an exact algorithm based on some optimal properties and the Lagrangian relaxation technique. We evaluate the performance of the proposed solution methods via computational experiments. The computational results show that the heuristics are efficient and effective in approximately solving large-sized instances of the problem, while the exact algorithm can only solve small-sized instances.

Keywords:

• scheduling
• order acceptance
• parallel machines
• profit

Acknowledgements

We thank the Editor, an Associate Editor, and five anonymous referees for their helpful comments on an earlier version of our paper. Wang was supported in part by the National Natural Science Foundation of China under grant number 71171114. Cheng was supported in part by the National Natural Science Foundation of China under grant number 71390334.