Much attention has been focused on the management in healthcare organization in recent years. Physician task scheduling will influence effects of safety, efficiency and satisfaction, which is very important for healthcare. The physician task scheduling problem can be formulated as a job shop scheduling problem (JSP). The JSP under stochastic process times (JSP-SPT) is more complex than a regular JSP because of uncertainties associated with the process. Classical approaches for solving the JSP-SPT ignored characteristics of uncertainty, which will spend more computing time of obtaining near-optimal solutions. To solve the JSP-SPT efficiently, an algorithm that integrates the artificial immune system with ordinal optimization, abbreviated as AISOO, is presented to search an excellent solution at low computational costs. Firstly, the JSP-SPT is presented as a stochastically constrained optimization problem. Secondly, the AIS is utilized to determine an excellent solution of the JSP-SPT to minimize the tardiness within a limited computing time. The AISOO method is employed to a JSP-SPT with 6 jobs and 6 machines. The stochastic process times are in exponential, truncated normal, and uniform probability distributions. Simulation results reveal that the excellent solution has significant improvements in computational efficiency, while maintaining reasonable solution quality.