Uniform Machine Scheduling Problem with Deteriorating Jobs and Rejection

Sheng Hua Zhao; Cheng Xin Luo

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

Paper Titles

Improve the Mechanisms Product Yield through Cycle Time Optimization
p.2409

Modular Production Network and the Development of Strategic Emerging Industries in China
p.2413

Research of Location Selection of Distribution Center for Service Based on Gravity Method
p.2419

Study on Decision-Making System and its Data Mining Application of Logistics Intelligent
p.2424

Uniform Machine Scheduling Problem with Deteriorating Jobs and Rejection
p.2429

The Design and Implementation of New Energy Enterprise Internal Control Evaluation System
p.2433

Fuzzy Evaluation on College English Teachers' Comprehensive Quality
p.2441

DEA-Based Efficiency Assessment of Railway Diversified Enterprises
p.2445

Research of the Condition and Strategy of the Network Information Literacy of the College Students
p.2449

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vols. 433-435Uniform Machine Scheduling Problem with...

Uniform Machine Scheduling Problem with Deteriorating Jobs and Rejection

Abstract:

In this paper, we consider uniform machine scheduling problem with deteriorating jobs and rejection. Each job's processing time is a linear nondecreasing function of its starting time. A job can be rejected by paying a penalty cost. The objective is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. We propose a fully polynomial-time approximation scheme (FPTAS), which shows that 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:

2429-2432

DOI:

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

Citation:

Cite this paper

Online since:

October 2013

Authors:

Sheng Hua Zhao, Cheng Xin Luo

Keywords:

Deterioration Effect, FPTAS, Make Span, Rejection, 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] R. L. Graham, E. L. Lawler , J. K. Lenstra, A. H. G. Rinnooy Kan. Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math., vol. 5 (1979), pp.287-326.

DOI: 10.1016/s0167-5060(08)70356-x

Google Scholar