This study deals with a scheduling problem with machine changeovers in a apparel company and presents a heuristic to minimize the total setup time subject to machine changeovers in models ordered. Commonly used heuristics such as shortest processing time and earliest due date can be used to calculate a feasible schedule quickly, but usually do not produce schedules that are close to optimal in these environments. A solution approach for the problem is developed by dividing it into two subproblems. Solution of the first problem is given as an input for the second problem. In this process, an originally developed heuristic is applied for the first problem and the second problem is formulated as an open and asymmetric traveling salesman problem. The second problem is solved by Genetic (GA) and Simulated Annealing (SA) algorithms. The experimental results demonstrate the effectiveness of the proposed algorithm to solve the scheduling problem with machine changeovers.