We discuss the optimization of photonic crystal waveguides for four-wave mixing applications, taking into account linear loss and free-carrier effects. Suitable figures-of-merits are introduced in order to guide us through the choice of practical, high efficiency designs requiring relatively low pump power and small waveguide length. In order to realistically perform the waveguide optimization process, we propose and validate an approximate expression for the four-wave mixing efficiency, which significantly alleviates our numerical calculations. Promising waveguide designs are identified by means of exhaustive search, altering some structural parameters. Our approach aims at optimizing the waveguides for nonlinear signalprocessing applications based on the four-wave mixing.