Nowadays, the demand of “personalization” and “multiple varieties and small batch production” in machining is increasing dramatically. The great challenges of scheduling are brought about by the high flexibility of production and the necessity of equipment maintenance, and the scheduling problems are more complex due to the deteriorating effect of the production process. In this paper, the processing time is described by the piecewise linear function. Based on the properties of the periodic maintenance and the flexible periodic maintenance, two scheduling models were established respectively to minimize the tardiness penalties and maintenance cost. The single machine scheduling problem with step-deteriorating jobs and fixed periodic maintenance strategy was studied. According to the numerical experiments and parameter analysis, the key factors and non-key factors of maintenance decision were determined. The result shows that flexible periodic maintenance has no idle time between adjacent batches, and can “adaptively” compensate for the penalty time due to deterioration, which performs better significantly than fixed periodic maintenance strategy.