مسيله‌ي بهينه‌سازي مقيد پذيرش و زمان‌بندي سفارشات دو عاملي با هدف بيشينه‌سازي مجموع سود

Constrained Optimization Problem of Two-agent Order Acceptance and Scheduling to Maximize Total Profit

در اين مقاله مسيله‌ي پذيرش و زمان‌بندي سفارشات با مسيله‌ي زمان‌بندي دوعاملي تركيب شده و يك مسيله‌ي كاربردي‌تر براساس نيازهاي متفاوت مشتريان مورد بررسي قرار گرفته است. لذا فرض شده كه دو دسته مشتري (عامل) وجود دارد و هدف بيشينه‌سازي مجموع سود سفارشات پذيرفته شده‌ي عامل اول به علاوه‌ي مجموع درآمد سفارشات پذيرفته شده‌ي عامل دوم است؛ به‌طوري كه هيچ سفارشي از عامل دوم ديركرد نداشته باشد. همچنين با اين فرض كه سفارش‌هاي عامل اول همگي داراي زمان پردازش يكسان هستند، نشان داده شده كه اين مسيله NP-hard است. در حالت معلوم بودن سفارشات پذيرفته شده، يك الگوريتم چندجمله‌يي براي تعيين توالي بهينه‌ي سفارشات، ارايه شده و براي حل مسيله‌ي اصلي نيز يك الگوريتم ابتكاري و يك برنامه‌ريزي پوياي شبه‌چندجمله‌يي توسعه داده شده است. نتايج نشان مي‌‌دهد كه %93.65 از مسايل تا ابعاد 150 سفارش به‌صورت بهينه حل شده است.

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.