Single Machine Scheduling with Discretely Compressible Processing Times

Shu Xia Zhang; Yu Zhong Zhang

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

Paper Titles

Selection of Engineering Management University Internship Projects Based on Fuzzy Analytic Hierarchy Process
p.1002

The (G'/G,1/G)-Expansion Method for Solving the (2+1)-Dimensional Breaking Soliton Equations
p.1006

Wireless Sensor Network Platform Based on STM32
p.1011

How to Identify the Real Requirement of Consumers
p.1017

Single Machine Scheduling with Discretely Compressible Processing Times
p.1020

An Efficient Image Retrieval Based on Combined Features
p.1025

Research on Passenger Information System Based on Train Security Detection Sensor Network
p.1030

The Vegetable Quality and Safety Traceability Model Research in China
p.1034

An APIT Algorithm Based on DV-HOP Multi-Hop
p.1038

HomeAdvanced Materials ResearchAdvanced Materials Research Vol. 787Single Machine Scheduling with Discretely...

Single Machine Scheduling with Discretely Compressible Processing Times

Abstract:

In this paper, we address the single machine scheduling problem with discretely compressible processing times, where processing any job with a compressed processing time incurs a corresponding compression cost. We consider the following problem: scheduling with discretely compressible processing times to minimize makespan with the constraint of total compression cost. Jobs may have different release times. We design a pseudo-polynomial time algorithm by approach of dynamic programming and an FPTAS.

You might also be interested in these eBooks

Advanced Materials Researches, Engineering and Manufacturing Technologies in Industry

View Preview

Info:

Periodical:

Advanced Materials Research (Volume 787)

Pages:

1020-1024

DOI:

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

Citation:

Cite this paper

Online since:

September 2013

Authors:

Shu Xia Zhang, Yu Zhong Zhang

Keywords:

Dynamic Programming, FPTAS, Scheduling

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

References

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

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

Google Scholar

[2] Z. Chen, Q. Lu and G. Tang: Single machine scheduling with discretely controllable processing times. Operations Research Letters, 21, 1997, 69-76.

DOI: 10.1016/s0167-6377(97)00010-2

Google Scholar

[3] R.G. Vickson: Two single machine sequencing problems involving controllable job processing times. AIIE Transactions, 12, 1980, 258-262.

DOI: 10.1080/05695558008974515

Google Scholar

[4] R.L. Daniels, J.B. Mazzola: Flow shop scheduling with resource flexibility. Operations Research, 42, 1994, 504-522.

DOI: 10.1287/opre.42.3.504

Google Scholar

[5] B. Chen, C.N. Potts and G.J. Woeginger: A review of machine scheduling: complexity, algorithms and approximability. Handbook of Combinatorial Optimization, edited by D.Z. Du and P.M. Pardalos, 21-169, 1998, Kluwer Academic Publishers.

DOI: 10.1007/978-1-4613-0303-9_25

Google Scholar

[6] Z. Cao, Z. Wang, Y. Zhang and S. Liu: On several scheduling problems with rejection or discretely compressible processing times. Lecture Notes in Computer Science, 3959, 2006, 90-98.

DOI: 10.1007/11750321_8

Google Scholar

[7] C.K. Poon, P. Zhang: Minimizing makespan in batch machine scheduling. Algorithmica, 39, 2004, 1-20.

DOI: 10.1007/s00453-004-1083-4

Google Scholar