Virtual manufacturing has 2 characteristics as an agent-based electronic commerce environment: dynamic nature of resource status and variety of agents' decision-making (i.e., scheduling) model. To reflect the characteristics, a relevant negotiation protocol should be designed and an appropriate decision-making model should be developed. In this article, from the perspective of a sales agent that is a middle man between customers and manufacturers in a virtual manufacturing environment, we provide a case study that suggests a time-bound framework for external negotiation between sales agents and customer agents, and internal cooperation between sales agents and manufacturing agents. We assume a job shop as the production model of a virtual manufacturing enterprise and formulate the optimal order selection problem with mixed integer programming, but its computation time is not acceptable for real-world problems. For this time-constrained decision making, we develop a genetic algorithm as an any-time problem-solving method for the scheduling of the production model, which shows a reasonable computation time for real-world cases and good incremental problem-solving capability.