Scheduling Problem for Parallel Machines with Limited Processing Capacities

Jing Fan

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

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

HomeAdvanced Materials ResearchAdvanced Materials Research Vol. 382Scheduling Problem for Parallel Machines with...

Scheduling Problem for Parallel Machines with Limited Processing Capacities

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:

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