In recent decades, manufacturers’ intense competitiveness to suit consumer expectations has compelled them to abandon the conventional workflow in favour of a more flexible one. This new trend increased the importance of master production schedule and make-to-order (MTO) strategy concepts. The former improves overall planning and controls complexity. The latter enables the production businesses to reinforce their flexibility and produce customized products. In a production setting, fluctuating resource capacity restricts production line performance, and ignoring this fact renders planning inapplicable. The current research work addresses the MPS problem in the context of the MTO production environment. The objective is to resolve Rough-Cut Capacity Planning by considering resource capacity fluctuation to schedule the customer’s order with the minimum cost imposed by the company and customer side. Consequently, this study is an initial attempt to propose a mathematical programming approach, which provides the optimum result for small and medium-size problems. Regarding the combinatorial intrinsic of this kind of problem, the mathematical programming approach can no longer reach the optimum solution for a large-scale problem. To overcome this, an innovative agent-based heuristic has been proposed. Computational experiments on variously sized problems confirm the efficiency of the agent-based approach.