The deadline scheduling problem, in its most generic setting, is the scheduling of jobs with different workloads and deadlines for completion. Typically, not enough servers are available to satisfy all the demand; the cost of processing may vary with time and unfinished jobs incur penalties. In this project, we are interested in the stochastic deadline scheduling problem where key parameters of the problem such as job arrivals,workloads, deadlines of completion, and processing costs are stochastic. In particular, we consider the problem of maximizing discounted rewards over an infinite scheduling horizon. A prototype application of such a problem is the charging of electric vehicles (EVs) at a charging service center. In such applications, EVs arrive at the service center randomly, each with its charging demand and deadline for completion. The charging cost depends on the cost of electricity at the time of charging, and a penalty is imposed when the service provider is unable to fulfill the request. Similar applications include the scheduling of packet transmission for real-time wireless networks, of jobs at data centers, of nursing personnel in hospitals, for internet streaming, and at customer service centers.