As machine maintenance is required in many industries, it is usually arranged in a planned schedule. How to schedule maintenance becomes especially important when achieving high shop performance is desired. In this study, we consider the maintenance scheduling problem in a textile company where different maintenance situations exist. The proposed algorithm, for five specific situations, is presented for the company to minimize the number of tardy jobs. Computational results based on real industrial data are provided to demonstrate the effectiveness of the algorithms.