Hi , I am of the opinion that Yes Tds is required to be deducted on advance payment too , because words used in the section 194C is "Payment made to residents ". And payment includes advance and the final payment .
TDS is to be mandatory either actual cash/cheque payment or credit to the account of Cotractor(Deductee), which ever is earlier. Advance to Contractor is liable to TDS, but when you make journal entry, you should consider/minus the earlier TDS.