عنوان مقاله [English]
In the operations research literature, the order acceptance and scheduling problem has been considered as a practical subject by researchers for a long time. This problem has been studied with various assumptions. In all previous studies of the literature it is assumed that manufacturers treat according to one type of penalty function with customers. But, in the real life situations, requests of customers are different and the manufacturers deal with different customers. So, in this paper it was attempted to tackle this deficiency by combining order acceptance and scheduling problem and multi-agent scheduling problem. So, it is assumed that two types of customers or agents exist such that the first agent gives penalty for tardiness and pays reward for earliness of its orders. But, for the second agent, tardiness of its orders is not acceptable. The problem objective function which is considered in this paper is maximizing the sum of profit of the first agent accepted orders in addition to sum of revenue of the second agent accepted orders such that no orders of the second agent are tardy. Besides, it is assumed that all of the first agent orders have equal processing time. It was shown that this problem is NP-hard in ordinary sense and in order to solve this problem, a heuristic algorithm and a pseudo-polynomial dynamic programming algorithm were proposed. To investigate the performance of these algorithms, their results of solving some problem instances were studied and to analyze the effects of factors, which were used in designing the problem instances, analysis of variance technique was applied. The results confirm the ability of dynamic programming algorithm in solving optimally 93.65% of instances up to 150 orders size within 3600 seconds. Besides, all instances with 60 orders size, 96.09% of instances with 100 orders size and 84.84% of instances with 150 orders size were solved optimally within 3600 seconds. In addition, the average relative percentage deviation of heuristic algorithm is 4.82%, which is shown the good performance of this algorithm.