An Optimal Algorithm for Scheduling with Variable Job Processing Times and Rejection

Ji Bo Wang; Chou Jung Hsu

doi:10.4028/www.scientific.net/AMM.775.449

Paper Titles

A Numerical Method for Calculating Fractional Derivative
p.426

Algorithms for Maximum Leaf Spanning Tress of Edge-Growing Network Models in Information System
p.431

Smartphone Based Classification System for Indoor Navigation
p.436

Development of Methods and Algorithms to Identify Real-Time Features of the Time-Frequency Characteristics of Electromagnetic Radiation in the Digital Data Radio Receiver
p.441

An Optimal Algorithm for Scheduling with Variable Job Processing Times and Rejection
p.449

Development of a Process Analysis System Oriented to Discrete Manufacturing Industry
p.453

Application of Ontology in Event-Driven Job-Shop Scheduling Problems
p.458

Applying Process Capability Analysis in Paint Industry
p.464

Influencing Factors of Manufacturing Upgrade in Zhejiang Province Based on Global Value Chain
p.468

HomeApplied Mechanics and MaterialsApplied Mechanics and Materials Vol. 775An Optimal Algorithm for Scheduling with Variable...

An Optimal Algorithm for Scheduling with Variable Job Processing Times and Rejection

Abstract:

This paper studies a single machine scheduling problem with rejection. Each job has a variable processing time and a rejection penalty. The objective function is to minimize the sum of the makespan of the accepted jobs and the total rejection penalty of the rejected jobs. We show that the problem can be solved in polynomial time.

You might also be interested in these eBooks

Engineering Solutions for Industrial Production

View Preview

Info:

Periodical:

Applied Mechanics and Materials (Volume 775)

Pages:

449-452

DOI:

https://doi.org/10.4028/www.scientific.net/AMM.775.449

Citation:

Cite this paper

Online since:

July 2015

Authors:

Ji Bo Wang, Chou Jung Hsu*

Keywords:

Deteriorating Jobs, Learning Effect, Rejection, Scheduling

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] S. Gawiejnowicz, Time-dependent scheduling, Springer, Berlin, (2008).

Google Scholar

[2] D. Biskup, A state-of-the-art review on scheduling with learning effects, European Journal of Operational Research, 188 (2008) 315-329.

DOI: 10.1016/j.ejor.2007.05.040

Google Scholar

[3] J. -B. Wang, A note on scheduling problems with learning effect and deteriorating jobs, International Journal of Systems Science, 37 (2006) 827-833.

DOI: 10.1080/00207720600879260

Google Scholar

[4] J. -B. Wang, C. -J. Hsu, D. -L. Yang, Single-machine scheduling with effects of exponential learning and general deterioration, Applied Mathematical Modelling, 37(2013) 2293-2299.

DOI: 10.1016/j.apm.2012.05.022

Google Scholar

[5] J. -B. Wang, J. -J. Wang, Scheduling jobs with a general learning effect model, Applied Mathematical Modelling, 37 (2013) 2364–2373.

DOI: 10.1016/j.apm.2012.05.029

Google Scholar

[6] J. -B. Wang, J. -J. Wang, Flowshop scheduling with a general exponential learning effect, Computers and Operations Rearch 43 (2014) 292-308.

DOI: 10.1016/j.cor.2013.09.001

Google Scholar

[7] J. -B. Wang, M. -Z. Wang, Minimizing makespan in three-machine flow shops with deteriorating jobs, Computers and Operations Research, 40 (2013) 547-557.

DOI: 10.1016/j.cor.2012.08.006

Google Scholar

[8] D. Shabtay, N. Gaspar, M. Kaspl, A surveey on offline scheduling with rejection, Journal of Scheduling 16 (2013) 3-28.

Google Scholar

[9] H. Nian, Z. Mao, Single-machine scheduling with job rejection, deteriorating effects, and deteriorating maintenance activities, Mathematical Problems in Engineering 2013 (2013) 389120 (9 pages).

DOI: 10.1155/2013/389120

Google Scholar

[10] D. Shabtay, The single machine serial batch scheduling problem with rejection to minimize total completion time and total rejection cost, European Journal of Operational Research, 233 (2014) 64-74.

DOI: 10.1016/j.ejor.2013.08.013

Google Scholar

[11] J. Ou, X. Zhong, G. Wang, An improved heuristic for parallel machine scheduling with rejection, European Journal of Operational Research, 241 (2015) 653-661.

DOI: 10.1016/j.ejor.2014.09.028

Google Scholar

[12] R.L. Graham, E.L. Lawler, J.K. Lenstra and A.H.G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5 (1979), 287-326.

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

Google Scholar

[13] G.H. Hardy, J.E. Littlewood, G. Polya, Inequalities, Cambridge University Press, (1967).

Google Scholar