Paper Titles
Mix-P2P Architecture of Distributed Storage System Based on HDFS
p.92
The Design of Mining Equipment Operating Status Monitoring System
p.96
Design and Simulation of a-Si:H/nc-Si:H Tandem Solar Cells
p.100
Supply Chain Scheduling with Transportation Cost on a Single Machine
p.106
Scheduling Problem for Parallel Machines with Limited Processing Capacities
p.110
Intelligent Control in Gas Supply System for Power Generation with Low Concentration Gas
p.114
Planar Frieze and Crystallographic Patterns with a Polar Spin from Dynamics
p.119
Experimental Investigation of Oil Removal from a Cylindrical Chamber
p.123
Dynamics Simulation for Horizontal-Axis Wind Turbines
p.129

Scheduling Problem for Parallel Machines with Limited Processing Capacities

Article Preview

Abstract:

In the actual industrial engineering, machines used for processing need to be checked periodically to ensure that they can work efficiently. Thus, the novel scheduling problem for parallel machines with limited capacities is worth to study. The objective function is to maximize the last completion time of jobs. We show the problem is NP-hard at least. Furthermore, two approximation algorithms are presented, and algorithms' performances are considered through the experiments with large amounts of data.

You might also be interested in these eBooks
Advanced Research on Advanced Structure, Materials and Engineering View Preview

Info:

Periodical:

Advanced Materials Research (Volume 382)

Pages:

110-113

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.382.110

Citation:

Cite this paper

Online since:

November 2011

Authors:

Jing Fan

Keywords:

Approximation Algorithm, Industrial Engineering, NP-Hard, Parallel Machine, Scheduling Problem

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

© 2012 Trans Tech Publications Ltd. All Rights Reserved

Share:

Citation:

References

[1] S. Albers, M. Mitzenmacher: Average-Case Analyses of First Fit and Random Fit Bin Packing, Rand. Struc. Alg. Vol. 16(2000), p.240–259.

DOI: 10.1002/(sici)1098-2418(200005)16:3<240::aid-rsa2>3.0.co;2-v

Google Scholar

[2] M. Yue: A simple proof of the inequality FFD (L) ≤ 11/9 OPT (L) + 1, ∀L for the FFD bin-packing algorithm, Acta Math. Appl. Sini. Vol. 7 (1991), p.321–331.

DOI: 10.1007/bf02009683

Google Scholar

[3] B. Xia, Z. Tan: Tighter bounds of the First Fit algorithm for the bin-packing problem, Dis. Appl. Math. Vol. 158 (2010), p.1668–1675.

DOI: 10.1016/j.dam.2010.05.026

Google Scholar

[4] R. Michael, D. Garey, S. Johnson: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. p.226. (1979).

Google Scholar

[5] V. Poirriez, N. Yanev, R. Andonov: A Hybrid Algorithm for the Unbounded Knapsack Problem. Disc. Opt. Vol. 6(2009), p.110–124.

DOI: 10.1016/j.disopt.2008.09.004

Google Scholar

[6] S. Martello, P. Toth: Knapsack Problems: Algorithms and Computer Implementation, John Wiley and Sons Publishers (1990).

Google Scholar

[7] G. Plateau, M. Elkihel: A hybrid algorithm for the 0-1 knapsack problem, Meth. Oper. Res., Vol. 49(1985), p.277–293.

Google Scholar

[8] G. B. Dantzig: Discrete-Variable Extremum Problems, Oper. Res. Vol. 5, (1957), p.266–288.

Google Scholar

[9] W.X. Xing, L. Kokin: Capacitated single machine scheduling and its on-line heuristics. IIE Trans. Vol. 34 (2002), p.991–998.

DOI: 10.1080/07408170208928928

Google Scholar

[10] C. J. Liao, W. J. Che: Single-machine scheduling with periodic maintenance and non-resumable jobs. Comp. Oper. Res. Vol. 9(2003), p.1335–1347.

Google Scholar