There are many application queries on windows defined over a stream of tuples that must be processed within specified deadlines which are after the window end. Stream processing is usually done either on a tuple-by-tuple basis or in micro-batches. Processing queries over large windows using stream processing engines can be very inefficient since there is often a significant overhead per tuple or micro-batch. Conversely, processing all tuples at the end of the window may result in missed deadlines, and idling of system resources before the window end. We present scheduling schemes for queries on large windows, using large batches, and using priority schemes based on query deadlines and slack time. Our scheduling scheme handles multiple concurrent queries without any prior knowledge of the future query requirements. The proposed scheduling algorithms have been implemented as a custom scheduler, on top of Apache Spark. Our performance study with TPC-H queries shows that our approach of processing can achieve significant computation time reduction compared to naively using Spark Streaming and can also handle stringent deadline cases efficiently.