When dealing with real-world problems, it turns out that there are many specifics of the problem we are trying to solve. Since many algorithms that are being developed are evaluated and compared on test benchmark problems, they can simulate real-world problems up to some degree and specifics are not presumed and tested. To make algorithms efficient, such specifics need to be considered and included in the problem solving. In this paper, a real-world production scheduling problem is addressed. A typical approach with genetic algorithm turned out to be insufficient due to added complexity of many specifics. To successfully solve this problem, a memetic algorithm, which uses problem-specific local search procedures to improve solutions acquired by genetic algorithm, is proposed. It is shown that the use of such local search procedures can significantly improve the effectiveness and efficiency of the algorithm.