Polling day
The day on which the majority of electors cast their vote at a polling place. It must be a Saturday and at least 33 days after the issue of the writs.
http://www.aec.gov.au/_content/how/procedures/timetable.htm

What are the latest possible dates for the next federal election?
The latest date by which a combined House of Representatives and half-Senate election must be held is 16 April 2005.

What are the earliest possible dates for the next federal election?
Given that a half senate election cannot be held before 1 July 2004, the earliest possible date for a combined House of Representatives and half senate election would be 7 August 2004 (1st Saturday after the 33 days minimum period from 1 July 2004).