In this study, a decision problem for the planning of the fabric dyeing process of a factory that produces towels is discussed. Towel fabric bolts in different quantities and features belonging to different orders are dyed by batching under certain restrictions in multi-port dyeing machines. In this problem, three different objectives are aimed to be optimized: Total tardiness, total number of washes (number of sequence dependent setups), total machine fixed cost. Since the prioritization for the objectives is made clearly by the company officials, the lexicographic approach has been preferred as the solution. First, the integer programming model of the problem is created. Lexicographic optimization approach was applied for the solution of the model. Afterwards, an effective Lexicographic multi-objective Genetic Algorithm, which is an extension of the single-objective Genetic Algorithm, is proposed. The performance of both solution methods was tested with randomly generated problems. Comparative results showed that the proposed lexicographic multi-objective genetic algorithm gave effective results.