Propose a Polynomial Time Algorithm for Total Completion Time Objective

Abstract

In this study we integrate deteriorate jobs with repair&maintenance activity on a single machine scheduling subject to total completion time. This work has more than one motivation. First jobs are assigned to machines in an automated production line. Later to schedule the maintenance activities if needed to prevent machinery from breaking down later. There are some important mathematical models to solve this combination. However due to the complexity of the problem which is Np-hard a polynomial algorithm should be needed for solving large problems. Therefore this article introduces several polnomial algorithms to determine the order of things best. With using these algorithms it will be possible to determine where to assign to the schedule taking into account the number of maintenance activities required and their optimum total completion time.