A Branch-and-Bound Algorithm for Identical Parallel Machine Total Tardiness Scheduling Problem with preemption_

:::

詳目顯示

第 1 筆 / 總合 1 筆

/1頁

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

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

This article examines the problem of scheduling preemptive jobs on identical parallel machines to minimize total tardiness. The problem is known to be NP-ard. An efficien the uristicis developed for solving large-sized problems. A lower bound scheme is also presented. Both of the proposed heuristic and lower bound are incorporated into abranch-and bound algorithm to optimally solves mall-sized problems. Computational results are reported. The branch-and-ound lgorithm can handle roblems of up to 16 jobs and 5 machines in size with inareasonable a mount of time. The olution obtained by the heuristich as an average percentage deviation of 4.01% from the optimal value, hile the initial lower bound has an average percentage deviation of 41.55% from the optimal value. Moreover, the heuristic finds approved optimal solutions for more than 45% of the problem instances tested.

以文找文

期刊論文
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.	Bruno, J.、Coffman, E. G. Jr.、Sethi, R.(1974)。Scheduling independent tasks to reduce mean finishing time。Communication of the ACM，17，382-387。
3.	Lawler, E. L.、Labetoulle, J.(1978)。On Preemptive Scheduling of Unrelated Parallel Processors by Linear Programming。Journal of ACM，25，612-619。
4.	McNaughton, R.(1959)。Scheduling with deadlines and loss functions。Management Science，6，1-12。
5.	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。
6.	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。
7.	Baptiste, P.、Jouglet, A.、Savourey, D.(2008)。Lower bounds for parallel machine scheduling problems。International Journal of Operational Research，3，643-664。
8.	Berit, J.(2006)。Scheduling parallel jobs to minimize the makespan。Journal of Scheduling，9，433-452。
9.	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。
10.	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。
11.	Du, J.、Leung, J.-T.、Young, G.(1990)。Minimizing mean flow time with release time constraint。Theoretical Computer Science，75，347-355。
12.	Elmaghraby, S. E.、Park, S. H.(1974)。Scheduling jobs on a number of identical machines。A I I E Transactions，6，1-13。
13.	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。
14.	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。
15.	Kravchenko, S.、Werner, F.(2011)。Parallel machine problems with equal processing times: A survey。Journal of Scheduling，14，435-444。
16.	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。
17.	Leung, J.-T.、Young, G. H.(1990)。Preemptive scheduling to minimize mean weighted flow time。Information Processing Letters，34(1)，47-50。
18.	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。
19.	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。
20.	Shams, H.、Salmasi, N.(2014)。Parallel machine scheduling problem with preemptive jobs and transportation delay。Computers & Operations Research，50，14-23。
21.	Shim, S.-O.、Kim, Y.-D.(2007)。Scheduling on parallel identical machines to minimize total tardiness。European Journal of Operational Research，177，135-146。
22.	Slowinski, R.(1981)。Scheduling preemptive tasks on unrelated processors with additional resources。RAIRO Information，15，155-166。
23.	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。
24.	Azizoglu, M.(2003)。Preemptive scheduling on identical parallel machines subject to deadlines。European Journal of Operational Research，148，205-210。
25.	Kravchenko, S. A.、Werner, F.(2013)。Erratum to: Minimizing total tardiness on parallel machines with preemptions。Journal of Scheduling，16，439-441。
26.	Kravchenko, S. A.、Werner, F.(2012)。Minimizing total tardiness on parallel machines with preemptions。Journal of Scheduling，15，193-200。
27.	Mensendiek, A.、Gupta, J. N. D.、Herrmann, J.(2015)。Scheduling identical parallel machines with fixed delivery dates to minimize total tardiness。European Journal of Operational Research，243，514-522。
28.	Schaller, J.(2014)。Minimizing total tardiness for scheduling identical parallel machines with family setups。Computers & Industrial Engineering，72，274-281。
29.	Schaller, J.(2009)。Note on Shim and Kim's lower bounds for scheduling on identical parallel machines to minimize total tardiness。European Journal of Operational Research，197，422-426。
30.	Su, L. H.、Cheng, T. C. E.、Chou, F. D.(2013)。A minimumcost network flow approach to preemptive parallel-machine scheduling。Computers & Industrial Engineering，64，453-458。
31.	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，287-326。
32.	Yalaoui, Farouk、Chu, Chengbin(2002)。Parallel Machine Scheduling to Minimize Total Tardiness。International Journal of Production Economics，76(3)，265-279。
33.	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：Addison Wesley Publishing。

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

top

:::

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

無相關期刊論文

無相關博士論文

無相關書籍

無相關著作

1.	A Study on Nurse Day-Off Scheduling under the Consideration of Binary Preference
2.	Measuring Schedule Uncertainty for a Stochastic Resource-Constrained Project Using Scenario-Based Approach with Utility-Entropy Decision Model
3.	On Two-door Three-dimensional Container Packing Problem under Home Delivery Service
4.	Bi-Objective Optimization for Integrating Production and Preventive Maintenance Scheduling in Two-Stage Assembly Flow Shop Problem
5.	Minimizing the Number of Tardy Jobs on a Two-Stage Assembly Flowshop
6.	A Branch-and-Bound Algorithm for Identical Parallel-Machine Total Completion Time Scheduling Problem with Preemption and Release Times
7.	An Exploration on Debugging Performance for Software Reliability Growth Models with Learning Effects and Change-Points
8.	A Production Inventory Model for Vendor–Buyer Coordination with Quantity Discount, Backordering and Rework for Fixed Life Time Products
9.	A Rostering Optimization Model for Physician Scheduling in Medical Department--A Case Study in District Hospital
10.	Interpretive Structural Modeling and Path Analysis for Proposed Framework of Lean Supply Chain in Indian Manufacturing Industry
11.	Modified Single-Vendor Single-Buyer Supply Chain Model with Quality Loss for Product
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

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

詳目顯示

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