An FPTAS for Uniform Machine Scheduling to Minimize the Total Completion Time and the Total Rejection Penalty

Dan Wu; Cheng Xin Luo

doi:10.4028/www.scientific.net/AMM.433-435.2339

Paper Titles

Application of CFD Simulations in Studying Outdoor Wind Environment in Different Community Building Layouts and Open Space Designs
p.2317

Main Existing Problems and Respective Countermeasures of Ground-Source Heat Pump Technique Applications
p.2327

Comparative Analysis of Two Methods for Conduction Transfer Functions of Building Constructions
p.2331

An FPTAS for Uniform Parallel-Machine Scheduling Problem with Deteriorating Jobs and Rejection
p.2335

An FPTAS for Uniform Machine Scheduling to Minimize the Total Completion Time and the Total Rejection Penalty
p.2339

Research on Dynamic BOM Based on Manufacturing Resources of Supplier
p.2343

An Adaptive Assembly Scheduling Approach in Knowledgeable Manufacturing
p.2347

Application of Case Based Reasoning in Technology Industry Competency Development
p.2351

Research of Parts Inventory Classification and Management Strategy in Manufacturing Enterprises
p.2359

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 433-435An FPTAS for Uniform Machine Scheduling to...

An FPTAS for Uniform Machine Scheduling to Minimize the Total Completion Time and the Total Rejection Penalty

Abstract:

In this paper, we study the NP-hard problem of schedulingjobs onuniform machines to minimize the total completion time of the accepted jobs and the total rejection penalty of the rejected jobs. Each job's processing time is a simple linear increasing function of its starting time. A job can be rejected by paying a penalty cost. We propose a fully polynomial-time approximation scheme (FPTAS) to show the problem is NP-hard in the ordinary sense.

You might also be interested in these eBooks

Advances in Mechatronics and Control Engineering II

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volumes 433-435)

Pages:

2339-2342

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.433-435.2339

Citation:

Cite this paper

Online since:

October 2013

Authors:

Dan Wu, Cheng Xin Luo

Keywords:

Deterioration Effect, FPTAS, Rejection, Total Completion Time, Uniform Machine

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

[1] T. C. E. Cheng, L. Y. Kang, C. T. Ng. Due-date assignment and single machine scheduling with deteriorating jobs. J. Oper. Res. Soc., vol. 55 (2004), pp.198-203.

DOI: 10.1057/palgrave.jors.2601681

Google Scholar

[2] Liqi Zhang, Lingfa Lu, J. Yuan. Single machine scheduling with release dates and rejection. Eur. J. Oper. Res., vol. 198 (2009), pp.975-978.

DOI: 10.1016/j.ejor.2008.10.006

Google Scholar

[3] M.Y. Kovalyov,W. Kubiak. A fully polynomial approximation scheme for the weighted earliness-tardiness problem. Oper. Res., vol. 47 (1999), pp.757-761.

DOI: 10.1287/opre.47.5.757

Google Scholar

[4] M. Ji, T. C. E. Cheng. Parallel-machine scheduling with simple linear deterioration to minimize total completion time. Eur. J. Oper. Res., vol. 188 (2008), pp.342-347.

DOI: 10.1016/j.ejor.2007.04.050

Google Scholar

[5] Liying Kang, C. T. Ng. A note on a fully polynomial-time approximation scheme for parallel-machine scheduling with deteriorating jobs. Int. J. Prod. Econ., vol. 109 (2007), pp.180-184.

DOI: 10.1016/j.ijpe.2006.11.014

Google Scholar

[6] S. Li, J. Yuan. Parallel-machine scheduling with deteriorating jobs and rejection. Theor. Comput. Sci., vol. 411 (2010), pp.3642-3650.

DOI: 10.1016/j.tcs.2010.06.008

Google Scholar

[7] M. Liu, F. Zheng, C. Chu, J. Zhang. An FPTAS for uniform machine scheduling to minimize makespan with linear deterioration. J. Comb. Optim., vol. 23 (2012), pp.483-492.

DOI: 10.1007/s10878-010-9364-0

Google Scholar

[8] Zou Yuan, Zhang Yuzhong, Miao Cuixia. Uniform Parallel-Machine Scheduling with Time Dependent Processing Times. Journal of the Operations Research Society of China, vol. 1(2013), pp.239-252.

DOI: 10.1007/s40305-013-0014-y

Google Scholar