Cracking furnace is the core device for ethylene production. In practice, multiple ethylene furnaces are usually run in parallel. The scheduling of the entire cracking furnace system has great significance when multiple feeds are simultaneously processed in multiple cracking furnaces with the changing of operating cost and yield of product. In this paper, given the requirements of both profit and energy saving in actual production process, a multi-objective optimization model contains two objectives, maximizing the average benefits and minimizing the average coking amount was proposed. The model can be abstracted as a multi-objective mixed integer nonlinear programming problem. Considering the mixed integer decision variables of this multi-objective problem, an improved hybrid encoding non-dominated sorting genetic algorithm with mixed discrete variables (MDNSGA-II) is used to solve the Pareto optimal front of this model, the algorithm adopted crossover and mutation strategy with multi-operators, which overcomes the deficiency that normal genetic algorithm cannot handle the optimization problem with mixed variables. Finally, using an ethylene plant with multiple cracking furnaces as an example to illustrate the effectiveness of the scheduling results by comparing the optimization results of multi-objective and single objective model.