To create a production schedule that maximizes social surplus—the total utility of all participants—a provider must know the utility functions of the recipients. However, this information is private and cannot be directly observed. One approach is to ask recipients to report their utilities, but because they act to maximize their own benefits, they may not report truthfully. To address this, the Scheduling Auction framework has been proposed to encourage truthful reporting while maximizing social surplus. This framework is based on the Vickrey–Clarke–Groves (VCG) mechanism and satisfies four desirable properties: strategy-proofness, Pareto efficiency, weak budget balance, and individual rationality. A key drawback of the Scheduling Auction is its computational complexity; it requires solving \(R+1\) optimization problems, where \(R\) is the number of recipients. As \(R\) increases, finding a solution within a realistic timeframe becomes infeasible. Meta-heuristic approaches can address this computational challenge, but a naïve application can compromise the mechanism’s desirable properties. In this study, we propose a Genetic Algorithm (GA)-based approach with design features that theoretically ensure weak budget balance and individual rationality. We also introduce a method to suppress the benefit of simple misreporting, which we evaluate through computational experiments.