||In this research, we find the minimizing total completion time of a scheduling problem on parallel machines with consideration of machine eligibility, preventive maintenance and sequence-dependent setup times. In our problem, we have n non-preemptive jobs with their release times and sequence-dependent setup times on m parallel machines. Each machine cannot serve jobs at every time point, that is, we consider a preventive maintenance on each machine. Each job has its release time and a set of eligible machines, and also a sequence-dependent setup time which determined by current job and the previous job. In order to reduce CPU run time and memory while solving a scheduling problem by finding an optimal solution, we try to find out a near-optimal solution for the problem.|
We propose an approximation algorithm to solve our scheduling problem approximately. In the algorithm, we use methods which proposed by Woeginger (2000) and Kacem and Mahjoub (2009). At first, a dynamic program is presented to calculate output of partial schedule in each iteration. After mapping at the end of each iteration, we use trimming-the-state-space technique to trim outputs which are close to each other and left only one of these states in state space. Finally, at the end of the final iteration, we find the minimum objective value which is stored in the left states.
|| Alon N., Y. Azar, G. J. Woeginger, T. Yadid, “Approximation Schemes for Scheduling on Parallel Machines”, Journal of Scheduling, 1, 55–66, 1998.|
 Mellouli R., C. Sadfi, C. Chu and I. Kacem, “Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times”, European Journal of Operational Research, 197, 1150-1165, 2009.
 Pinedo M., Scheduling: Theory, Algorithm and System (3th ed.), New York: Prentice-Hall, 2008.
 Ruiz R., T. Stutzle, “An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives”, European Journal of Operational Research, 187, 1143-1159 , 2008.
 Kacem, I., Mahjoub, A. R., “Fully polynomial time approximation scheme for the weighted flow-time minimization on a single machine with a fixed non-availability interval”, Computers & Industrial Engineering, 1708-1712, 2009.
 Schuurman, P., Woeginger G. J.,.“Approximation schemes - a tutorial”, Manuscript, to appear in Lectures on Scheduling, edited by R.H. Mohring, C.N. Potts, A.S. Schulz, G.J. Woeginger and L.A. Wolsey, 2006.
 Vallada E., R. Ruiz, “A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times”, European Journal of Operational Research, 211, 612–622, 2011.
 Woeginger, G. J., “When does a dynamic programming formulation guarantee the existence of a fully poly nomial time approximation scheme (FPTAS)?”, INFORMS J. Comput., 12, 57-74, 2000.
 Belouadah, H., Potts, C. N., “Scheduling identical parallel machine to minimize total weighted completion time”, Discrete Applied Mathematics, 201–218, 1994.