| 摘要(英) |
In this research, we consider the problem of scheduling n preemptive jobs with distinct release time on m identical parallel machines under machine availability and eligibility constraints to minimize total completion time. To find the optimal solution, we propose a branch and bound algorithm. First, using the idea of time epochs which was proposed from Liao and Sheen (2008) to separate machine available intervals. Then adopt the branching scheme from Mellouli et al. (2009) to branch out a node by assigning an additional job on each available interval specified by two adjacent time epochs. Second, according to our bounding scheme, we develop an iterated heuristic upper bound based on bipartite matching algorithm to find an initial feasible upper bound. By relaxing the restriction of machine eligibility constraint, we used extended shortest remaining processing time (SRPT) which proposed from Yalaoui and Chu (2006) to solve the reduced problem optimally, and set the optimal solution of it to be our lower bound. Computational analysis shows that the efficiency of our branch and bound algorithm can eliminate unnecessary nodes up to 99%. Due to the result of the average percentage gap of our upper bound, it can show that this upper bound is not only a polynomial time bound but also a tight bound. |
| 參考文獻 |
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.
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.
Horn W.A. (1973) “Technical note-minimizing average flow time with parallel machines”, Operations Research, 21(3), 846-847.
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.
Lee C.Y. and C.Y. Chen (2000) “Scheduling jobs and maintenance activities on parallel machines”, Naval Research Logistics, 47, 145-165.
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.
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.
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.
Pinedo M. (2008) “Scheduling: Theory, Algorithm and System (3th ed)”, New York: Prentice-Hall.
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.
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.
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.
Wu L.E. (2013) “A Branch and Bound Algorithm for Parallel Machine Scheduling Problem with Machine Availability and Job Preemption Constraint”, 中央大學碩士論文.
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.
|
[Endnote RIS 格式]
[相關文章]
[文章引用]
[完整記錄]
[館藏目錄]
至系統瀏覽論文 ( 永不開放)
plurk
funp
live
udn
HD
myshare
netvibes
friend
youpush
delicious
baidu
Google bookmarks
del.icio.us
hemidemi
facebook
twitter
google
reddit