This paper proposes an adaptive-penalty Genetic Algorithm (GA) as a solution tool for determining the optimal number of doctors and appointment interval in an appointment system. The appointment system belongs to the class of individual block/fixed interval. To reflect the uncertainty, the length of service time for doctor consultation, the time required for the laboratory tests, and the time deviating from the appointment time are modelled by random variables, and no-show patients are considered. Using the adaptive penalty scheme, optimization constraints are automatically and numerically handled. The optimization results from the adaptive-penalty GA are verified and in agreement with those from direct simulations.