Integrating two-agent scheduling and order acceptance problems to maximise total revenue by bounding each agent penalty function

This paper integrates the two‐agent scheduling problem and the order acceptance and scheduling problem, to form a single problem for further investigation. The idea originates from real life situations in which manufacturers deal with different customers, each having different requests. It is, therefore, assumed in the new problem that two customer (agent) types exist while each has their specific penalty functions. The penalty function of the first agent is the total lateness while that of the second is the number of tardy orders. The objective is maximising the total revenue of accepted orders by bounding each agent's penalty function. For this problem, a pseudo‐polynomial dynamic programming algorithm is developed. It was shown that the algorithm is capable of optimally solving all the problem instances up to 50 orders in size. The algorithm is found to be capable of solving 87.15% of the instances with 90 orders.