Here are some papers I've been involved with over the years covering various sort of heuristic algorithms, including heuristics combined with human interaction. The first two are probably the most important and interesting, although the third on rectangle packing nicely shows how these ideas all work on a specific problem.

1. G. Klau, N. Lesh, J. Marks, and M. Mitzenmacher.
   Human-Guided Tabu Search
   Proceedings of the 18th National Conference on Artificial Intelligence, pp. 41-47, 2002.
   Abstract         Conference version (pdf)
   
   
2. N. Lesh and M. Mitzenmacher
   BubbleSearch: A Simple Heuristic for Improving Priority-Based Greedy Algorithms
   (Information Processing Letters, Volume 97, Issue 4, Pages 161-169, 28 February 2006.
   Journal version (pdf)
   
   
3. N. Lesh, J. Marks, A. McMahon, and M. Mitzenmacher.
   New Heuristic and Interactive Approaches to 2D Rectangular Strip Packing
   Journal of Experimental Algorithmics (JEA).
   Journal version (ps)
   Vol. 10, Article No. 1.2, 2005.
   
   
4. M. Chimani, N. Lesh, M. Mitzenmacher, and C. Sidner.
   A case study in large-scale interactive optimization.
   International Conference on Artificial Intelligence and Applications.
   Conference version (pdf)
   
   
5. N. Lesh, M. Mitzenmacher, and S. Whitesides
   A Complete and Effective Move Set for Simplified Protein Folding
   Proceedings of the 7th Annual Int'l Conference on Research in Computational Molecular Biology (RECOMB), 2003, pp. 188-195.
   Abstract         Conf. version (pdf).