Parallel Machine Scheduling Problem with a Resumable Availability Constraint

Qi Zhang; Cheng Xin Luo

doi:10.4028/www.scientific.net/AMR.1061-1062.708

Paper Titles

Design and Experimental Analysis of Pepper Fruit Preprocessing Machine
p.687

Design on a Removable Catalyst Muffler
p.692

Multi-Dimensional Assembly Process Data Management Method Based on Workflow
p.696

Research on System Architecture and Fine-Grained Access Control Strategy of Collaborative Development Platform
p.701

Parallel Machine Scheduling Problem with a Resumable Availability Constraint
p.708

Study on the Design Factors Affecting the Operating Actions that Can Be Used Easily at the Design Stage
p.712

The Design of Electrical Equipment Fault Diagnosis System Based on Fuzzy Inference
p.716

The Research of BDAR under Conditions of Informationalization
p.720

Influence of Running Shoes Made of Different Materials on Athletes’ Sprint Speed
p.724

HomeAdvanced Materials ResearchAdvanced Materials Research Vols. 1061-1062Parallel Machine Scheduling Problem with a...

Parallel Machine Scheduling Problem with a Resumable Availability Constraint

Abstract:

This paper considers a scheduling problem of two parallel machines with a resumable availability constraint. The objective is to minimize the makespan. The problem is NP-hard in the ordinary sense. Therefore, we need to find an approximate solution that fulfills the required error bound. To get a better approximation solution in a polynomial running time, we propose a fully polynomial-time approximation scheme (FPTAS) by trimming states space.

You might also be interested in these eBooks

Research in Materials and Manufacturing Technologies IV

View Preview

Info:

Periodical:

Advanced Materials Research (Volumes 1061-1062)

Pages:

708-711

DOI:

https://doi.org/10.4028/www.scientific.net/AMR.1061-1062.708

Citation:

Cite this paper

Online since:

December 2014

Authors:

Qi Zhang*, Cheng Xin Luo

Keywords:

Approximate Algorithm, Non-Availability Interval, NP-Hard, Parallel Machine, Resumable

Export:

RIS, BibTeX

Price:

Permissions CCC:

Request Permissions

Permissions PLS:

Request Permissions

Сopyright:

Citation:

* - Corresponding Author

References

[1] G. Schmid. Scheduling on semi-identical processors. ZOR Z Operations Research. Vol. 28 (1984), pp.153-162.

Google Scholar

[2] C-Y Lee, S.D. Liman. Capacitated two-parallel machines scheduling to minimize sum of job completion times. Discrete Applied Mathematics. Vol. 41(1993), pp.211-222.

DOI: 10.1016/0166-218x(90)90055-h

Google Scholar

[3] G. Mosheiov, D. Oron. Due-date assignment and maintenance activity scheduling problem. Math Comput Modeling, Vol. 44 (2006), pp.1053-1057.

DOI: 10.1016/j.mcm.2006.03.008

Google Scholar

[4] I. Kacem. Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date. Discrete Appl Math, Vol. 158(2010), pp.1035-1040.

DOI: 10.1016/j.dam.2010.01.013

Google Scholar

[5] I. Kacem. Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval. J Comb Optim, Vol. 17(2009), pp.117-133.

DOI: 10.1007/s10878-007-9102-4

Google Scholar

[6] C-Y Lee. Machine scheduling with an availability constraint. Journal of glob aloptimization. Vol. 9(1996), pp.395-416.

Google Scholar

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

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

Google Scholar