How to index these queries effectively

I have an area of my app where a lot of complex queries are being performed, returning 10s of records per page out of a table of 1000s. Here are some samples.

SELECT `tasks`.* FROM `task开发者_如何学Cs` WHERE (`tasks`.company_id = 21) AND (employee_id IS NULL) AND (status != 'Complete') AND (status != 'Cancelled') ORDER BY scheduled desc LIMIT 0, 30;

SELECT `tasks`.* FROM `tasks` WHERE (`tasks`.company_id = 21) AND (employee_id = 0) AND (status != 'Complete') AND (status != 'Cancelled') AND (scheduled IS NOT NULL) AND (scheduled > '2011-03-28' AND scheduled < '2011-09-28');

SELECT `tasks`.* FROM `tasks` WHERE (`tasks`.employee_id = 27) AND (status != 'Complete') AND (status != 'Cancelled') ORDER BY scheduled desc LIMIT 0, 30

employee_id and status are always present; company_id is nearly always present, and scheduled is just the default ordering, which the user can change.

I tried these indexes:

# ignored for some reason - did not seem to build successfully in the db
add_index :tasks, [:company_id, :employee_id, :status, :scheduled]

# db favorite, but often results in FILESORT
add_index :tasks, [:employee_id, :status, :scheduled]

What is the best way to deal with my problem and reduce the number of FILESORTS I'm getting on these queries?

Please let me know if I can provide any more detailed information.