We present an interactive multi-criteria procedure that uses user defined tradeoff-cutting planes to identify promising feasible solution search space. New solutions in the promising feasible solution search space are constructed using combination of scatter and random search. The procedure of identifying tradeoff-cutting planes and scatter search continues for either a predetermined fixed number of iterations or until no solutions in the promising feasible solution search space are found. We formulate a coal production planning problem with fuzzy profit and fuzzy coal quality decision-maker utilities, and apply our procedure for additive and multiplicative decision-maker utilities