A Branch-and-Bound Algorithm for Identical Parallel-Machine Total Completion Time Scheduling Problem with Preemption and Release Times_

:::

詳目顯示

第 1 筆 / 總合 1 筆

/1頁

來源文獻資料
外文摘要
引文資料

題名：	A Branch-and-Bound Algorithm for Identical Parallel-Machine Total Completion Time Scheduling Problem with Preemption and Release Times
書刊名：	工業工程學刊
作者：	Liaw, Ching-fang
出版日期：	2016
卷期：	33:6
頁次：	頁383-390
主題關鍵詞：	Scheduling；Parallel-machine；Branch-and-bound；Preemption；Release time
原始連結：	連回原系統網址
相關次數：	被引用次數:期刊(0) 博士論文(0) 專書(0) 專書論文(0) 排除自我引用:0 共同引用:0 點閱:22

This article examines the problem of scheduling preemptive jobs with release times on identical parallel machines to minimize total completion time. The problem is known to be NP-hard. An efficient heuristic is developed for solving large-sized problems. A lower bound scheme is also presented. Both of the proposed heuristic and lower bound are incorporated into a branch-and-bound algorithm to optimally solve small-sized problems. Computational results are reported. The branch-and-bound algorithm can handle problems of up to 11 jobs and 4 machines in size within a reasonable amount of time. The solution obtained by the heuristic has an average percentage deviation of less than 0.18% from the optimal value, while the initial lower bound has an average percentage deviation of less than 5.36% from the optimal value. Moreover, the heuristic finds approved optimal solutions for over 80% of the problem instances completely solved.

以文找文

期刊論文
1.	Lenstra, J. K.、Rinnooy Kan, A. H. G.、Brucker, P.(1977)。Complexity of machine scheduling problems。Annals of Discrete Mathematics，1，343-362。
2.	Graham, R. L.、Lawler, E. L.、Lenstra, J. K.、Rinnooy Kan, A. H. G.(1979)。Optimization and Approximation in Deterministic Sequencing and Scheduling: A Survey。Annals of Discrete Mathematics，5(2)，287-326。
3.	Hariri, A. M. A.、Potts, C. N.(1983)。An algorithm for single machine sequencing with release dates to minimize total weighted completion time。Discrete Applied Mathematics，5(1)，99-109。
4.	Bruno, J.、Coffman, E. G. Jr.、Sethi, R.(1974)。Scheduling independent tasks to reduce mean finishing time。Communication of the ACM，17，382-387。
5.	Lawler, E. L.、Labetoulle, J.(1978)。On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming。Journal of ACM，25，612-619。
6.	McNaughton, R.(1959)。Scheduling with deadlines and loss functions。Management Science，6，1-12。
7.	Azizoglu, M.、Kirca, O.(1999)。On the minimization of total weighted flow time with identical and uniform parallel machines。European Journal of Operational Research，113，91-100。
8.	Baptiste, P.、Brucker, P.、Chrobak, M.、Dürr, C.(2007)。The complexity of mean flow time scheduling problems with release times。Journal of Scheduling，10，139-146。
9.	Baptiste, P.、Jouglet, A.、Savourey, D.(2008)。Lower bounds for parallel machine scheduling problems。International Journal of Operational Research，3，643-664。
10.	Berit, J.(2006)。Scheduling parallel jobs to minimize the makespan。Journal of Scheduling，9，433-452。
11.	Blazewicz, J.、Cellary, W.、Slowinski, R.、Weglarz, J.(1976)。Deterministic problem of scheduling tasks on parallel processors, Part 1: Set of independent tasks。Podstawy Sterowania，6，155-178。
12.	Brucker, P.、Kravchenko, S. A.(2008)。Scheduling jobs with equal processing times and time windows on identical parallel machines。Journal of Scheduling，11，229-237。
13.	Du, J.、Leung, J.-T.、Young, G.(1990)。Minimizing mean flow time with release time constraint。Theoretical Computer Science，75，347-355。
14.	Elmaghraby, S. E.、Park, S. H.(1974)。Scheduling jobs on a number of identical machines。A I I E Transactions，6，1-13。
15.	Haned, Amina、Soukhal, Ameur、Boudhar, Mourad、Tuong, Nguyen Huynh(2012)。Scheduling on parallel machines with preemption and transportation delays。Computers & Operations Research，39(2)，374-381。
16.	Horn, W. A.(1974)。Some simple scheduling algorithms。Naval Research Logistics Quarterly，21，177-185。
17.	Kawaguchi, T.、Kyan, S.(1986)。Worst case bound of an LRF schedule for the mean weighted flow-time problem。SIAM Journal on Computing，15，1119-1129。
18.	Kravchenko, S.、Werner, F.(2011)。Parallel machine problems with equal processing times: A survey。Journal of Scheduling，14，435-444。
19.	Lee, C. Y.、Uzsoy, R.(1992)。A new dynamic programming algorithm for the parallel machines total weighted completion time problem。Operations Research Letters，11，73-75。
20.	Leung, J.-T.、Young, G. H.(1990)。Preemptive scheduling to minimize mean weighted flow time。Information Processing Letters，34(1)，47-50。
21.	Prot, D.、Bellenguez-Morineau, O.、Lahlou, C.(2013)。New complexity results for parallel identical machine scheduling problems with preemption, release dates and regular criteria。European Journal of Operational Research，231，282-287。
22.	Sarin, S. C.、Ahn, S.、Bishop, A. B.(1988)。An improved branching scheme for the branch and bound procedure of scheduling n jobs on m parallel machines to minimize total weighted flowtime。International Journal of Production Research，26，1183-1191。
23.	Shams, H.、Salmasi, N.(2014)。Parallel machine scheduling problem with preemptive jobs and transportation delay。Computers & Operations Research，50，14-23。
24.	Shim, S.-O.、Kim, Y.-D.(2007)。Scheduling on parallel identical machines to minimize total tardiness。European Journal of Operational Research，177，135-146。
25.	Slowinski, R.(1981)。Scheduling preemptive tasks on unrelated processors with additional resources。RAIRO Information，15，155-166。
26.	Tanaka, S.、Araki, M.(2008)。A branch-and-bound algorithm with Lagrangian relaxation to minimize total tardiness on identical parallel machines。International Journal of Production Economics，113，446-458。
27.	Yalaoui, Farouk、Chu, Chengbin(2002)。Parallel Machine Scheduling to Minimize Total Tardiness。International Journal of Production Economics，76(3)，265-279。
28.	Azizoglu, Meral、Kirca, Omer(1998)。Tardiness Minimization on Parallel Machines。International Journal of Production Economics，55(2)，163-168。

圖書
1.	Conway, R. W.、Maxwell, W. L.、Miller, L. W.(1967)。Theory of scheduling。Reading, MA：New York：Addison-Wesley：Wiley。

圖書論文
1.	Kravchenko, S.、Werner, F.(2012)。Minimizing a regular function on uniform machines with ordered completion times。Linear Programming--New Frontiers in Theory and Applications。Budapest University of Technology and Economics。

推文
推薦
引用網址
引用嵌入語法
轉寄

top

:::

相關期刊
相關論文
相關專書
相關著作
熱門點閱

無相關期刊論文

無相關博士論文

無相關書籍

無相關著作

1.	A Branch-and-Bound Algorithm for Identical Parallel Machine Total Tardiness Scheduling Problem with preemption
2.	Bi-Objective Optimization for Integrating Production and Preventive Maintenance Scheduling in Two-Stage Assembly Flow Shop Problem
3.	Minimizing the Number of Tardy Jobs on a Two-Stage Assembly Flowshop
4.	An Exploration on Debugging Performance for Software Reliability Growth Models with Learning Effects and Change-Points
5.	A Study on Nurse Day-Off Scheduling under the Consideration of Binary Preference
6.	A Production Inventory Model for Vendor–Buyer Coordination with Quantity Discount, Backordering and Rework for Fixed Life Time Products
7.	Measuring Schedule Uncertainty for a Stochastic Resource-Constrained Project Using Scenario-Based Approach with Utility-Entropy Decision Model
8.	A Rostering Optimization Model for Physician Scheduling in Medical Department--A Case Study in District Hospital
9.	Interpretive Structural Modeling and Path Analysis for Proposed Framework of Lean Supply Chain in Indian Manufacturing Industry
10.	Modified Single-Vendor Single-Buyer Supply Chain Model with Quality Loss for Product
11.	On Two-door Three-dimensional Container Packing Problem under Home Delivery Service
12.	A Computational Analysis of the Impact of Correlation and Data Translation on DEA Efficiency Scores
13.	Slide Operation Method for a Touch Screen--The Concept of Connecting Audio Component
14.	Bi-objective Closed-loop Supply Chain Network Design with Risks in a Fuzzy Environment

QR Code

臺灣人文及社會科學引文索引資料庫系統

詳目顯示

臺灣人文及社會科學引文索引資料庫