We discuss the optimization of photonic crystal waveguides for four-wave mixing (FWM) applications, taking into account linear loss and free-carrier effects. Suitable figures of merit 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 FWM efficiency, which significantly alleviates our numerical calculations. Promising waveguide designs are identified by means of an exhaustive search, altering some structural parameters. Our approach aims to optimize the waveguides for nonlinear signal-processing applications based on the FWM.