Summary: The fuzzy sets theory advanced by Zadeh in 1965 has been useful in the development and application of such fields as fuzzy control, artificial intelligence, and expert systems. Application of fuzzy sets theory to operations research is an important and promising undertaking, but there have been few generalized studies on combinatorial optimization by fuzzy sets theory beside the work of the present author and his colleagues. As far as we know, Chanas and Kotodziejcyzk were the first to introduce the idea of fuzzy capacity into network flow problems. Their work motivated us to initiate the present study on fuzzy combinatorial optimization. We also wanted to work on the so-called NP-complete problem, where no efficient calculation solution exists for nearly all of combinatorial optimization problems. We propose to relax conditions and constraints in order to find easier solutions in a realistic sense by fuzzification. We would like to employ such problems as the fuzzy scheduling problem and the fuzzy network problem, but, unfortunately, while there are many models of minimum degree of satisfaction-optimization similar to decision making in a fuzzy environment and there are many partial attempts which constitute an introduction to combinatorial optimization of generalized fuzzy planning, current studies (our own included) can only fuzzify cases where original problems can be solved to some extent.