||In most scheduling problem, machines are always continuously available to process jobs all the time. However, it usually exist unavailable time intervals for routine maintenance in practice. Besides, some job is suitable for specific machines to process based on the property of job. In this study, we consider the problem of scheduling n non-preemptive jobs with distinct release time on m identical parallel machines under machine availability and eligibility constraints to minimize total completion time.|
For the scheduling problem, we use branch and bound method to find the optimal solution. In the branch and bound algorithm, we discuss two way of branching. First one is, we adopted the branching scheme from Mellouli et al. (2009) which concept is through assigning an additional job on each available interval. We also propose the other approach of branching which contained the concept of forward scheduling. Based on the branching scheme we proposed, we also propose a dominance rule to eliminate redundant nodes. We adopted the property in Yalaoui and Chu (2006) which could solve the reduced problem by relaxing the restriction of machine eligibility constraint and allow jobs split, and let the optimal solution to be our lower bound.
Hmid S.D.R. and T.T. Mohammad (2008). “Study of Scheduling Problems with Machine Availability Constraint”, Journal of Industrial and Systems Engineering, 1(4), 360-383.
Sanlaville E. and G. Schmidt (1998). “Machine scheduling with availability constraints”, Acta Informatica, 35, 795-811.
Schmidt G. (2000). “Scheduling with limited machine availability”, European Journal of Operational Research, 121, 1-15.
Centeno G. and R.L. Armacost (1997). “Parallel machine scheduling with release time and machine eligibility restrictions”, Computers & industrial engineering, 33 (1), 273-276.
Yalaoui F. and C. Chu (2006). “New exact method to solve the P_m |r_j |∑▒C_j schedule problem”, Int. J. Production Economics, 100, 168-179.
Brucker P. and S.A. Kravchenco (2008). “Scheduling jobs with equal processing times and time windows on identical parallel machines”, Journal of Scheduling, 11, 229-237.
Horn W.A. (1973). “Technical note-minimizing average flow time with parallel machines”, Operations Research, 21(3), 846-847.
Adiri I., J. Bruno, E. Frostig and A.H.G. Rinnooykan (1989). “Single machine flow-time scheduling with a single breakdown”, ACTA Information, 26,679-696.
Kacem I., C. Chu and A. Souissi (2006). “Single-machine scheduling with an availability constraint to minimize the weighted sum of the completion times”, Computers and Operations Research, 180, 396-405.
Mellouli R., C. Sadfi, C. Chu and I. Kacem (2009). “Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times”, European Journal of Operational Research, 197, 1150-1165.
Pinedo M. (2008). “Scheduling: Theory, Algorithm and System (3th ed)”, New York: Prentice-Hall.
Centeno G. and R.L. Armacost (2004). “Minimizing makespan on parallel machines with release time and machine eligibility restrictions”, International Journal of Production Research, 42(6), 1243-1256.
Liao L.W. and G.J Sheen (2008). “Parallel machine scheduling with machine availability and eligibility constraints”, European Journal of Operational Research, 184, 458–467.
Lee C.Y. and Z.L. Chen (2000). “Scheduling jobs and maintenance activities on parallel machines”, Naval Research Logistics, 47, 145-165.
Nessah N., C. Chu and F. Yalaoui (2007). “An exact method for P_m |sds,r_i |∑_(i=1)^n▒C_i problem”, Computers and Operations Research, 34, 2840-2848.
Qi X., T. Chen and F. Tu (1999). “Scheduling the maintenance on a single machine”, The Journal of the Operation Research Society, 50, 1071-1078.
Shim S.O. and Y.D. Kim (2008). “A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property”, Computers and Operations Research, 35, 863-875.