Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
A Review and New Design Options to Minimize the Capital and Operational Cost of Single Effect Solar Absorption Cooling System for Residential Use Read chapter Read first chapter

2012 | OriginalPaper | Chapter

Complexity on Parallel Machine Scheduling: A Review

Author : D. K. Behera

Published in: Emerging Trends in Science, Engineering and Technology

Publisher: Springer India

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The intended audience is scheduling practitioners and theoreticians as well as beginners in the field of scheduling. The purpose of this paper is to review the area of parallel machine scheduling (PMS) on issues of complexity. A critical review of the methods employed and applications developed in this relatively new area are presented and notable successes are highlighted. The PMS algorithms are discussed. We have given up-to-date information on polynomially type of problems based on non-preemptive criteria. It is shown that parallel machine makespan-minimization problem is NP-hard even for the two-machine problem. Moreover, the two-machine problem can be solved by the pseudo polynomial algorithm.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter An Integrated Methodology for Geometric Tolerance Analysis and Value Specification Based on Arithmetical, Graphical and Analytical Methods
next chapter Design of Optimal Maintenance Strategy
Literature
1.
Mokotoff E (2001) Parallel machine scheduling problems: a survey. Asia-Pacific J Oper Res 18:193–242MathSciNetMATH
2.
Baker KR, Trietsch D (2009) Principles of sequencing and scheduling. Wiley, New york
3.
Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP completeness. Freeman, San FranciscoMATH
4.
Graham RL, Lawler EL, Lenstra JK, Kan AHGR (1979) Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann Discrete Math 5:287–326MathSciNetMATHCrossRef
5.
Karp RM (1972) Reducibility among combinatorial problems: complexity of computer computations. Plenum Press, New York, pp 85–103
6.
Lawler EL, Lenstra JK, Kan AHGR, Shmoys DB (1993) Sequencing and scheduling: algorithms and complexity. Handbooks in operations research and management science 4, logistics of production and inventory, North Holland, Amsterdam, pp 445–524
7.
Papadimitriou CH (1994) Computational complexity, Addison-Wesley, Boston
8.
Cheng T, Sin C (1990) A state-of-the-art review of parallel-machine scheduling research. Eur J Oper Res 47:271–292MATHCrossRef
9.
Filippi C, Romanin-Jacur G (2009) Exact and approximate algorithms for high-multiplicity parallel machine scheduling. J Sched 12:529–541MathSciNetMATHCrossRef
10.
Levner E (2007) Multiprocessor scheduling: theory and applications. Itech Education and Publishing, Vienna, p 436. ISBN 978-3-902613-02-8CrossRef
11.
12.
Chen CL (2009) A bottleneck-based heuristic for minimizing makespan in a flexible flow line with unrelated parallel machines. Comput Oper Res 35:3073–3081CrossRef
13.
Allahverdi A, Gupta JND, Aldowaisan T (1999) A review of scheduling research involving setup considerations. Omega 27:219–239CrossRef
14.
15.
Lee H, Guignard M (1996) Hybrid bounding procedure for the workload allocation problem on parallel unrelated machines with setups. J Oper Res Soc 47:1247–1261MATH
16.
Weng MX, Lu J, Ren H (2001) Unrelated parallel machine scheduling with setup consideration and a total weighted completion time objective. Int J Prod Econ 70:215–226CrossRef
17.
Bruno J, Sethi R (1978) Task sequencing in a batch environment with setup times. Found Control Eng 3:105–117MathSciNetMATH
18.
Behera DK, Laha D (2012) Comparison of heuristics for identical parallel machine scheduling. Adv Mater Res 488–489:1708–1712CrossRef
19.
Radhakrishnan S, Ventura JA (2000) Simulated annealing for parallel machine scheduling with earliness/tardiness penalties and sequence-dependent set-up times. Int J Prod Res 38:2233–2252MATHCrossRef
20.
21.
Kim DW, Kim KH, Jang W, Frank Chen F (2002) Unrelated parallel machine scheduling with setup times using simulated annealing. Rob Comput Integr Manufact 18:223–231CrossRef
22.
Koulamas C (1997) Decomposition and hybrid simulated annealing heuristics for the parallel-machine total tardiness problem. Nav Res Logistics 44:105–125CrossRef
23.
Izakian H, Abraham A, Snášel V Comparison of heuristics for scheduling independent tasks on heterogeneous distributed environments, collected from internet
24.
Armentano VA, Yamashita DS (2000) Tabu search for scheduling on identical parallel machines to minimize mean tardiness. J Intell Manufact 11:453–460CrossRef
25.
Park MW, Kim YD (1997) Search heuristics for a parallel machine scheduling problem with ready times and due dates. Comput Ind Eng 33:793–796CrossRef
26.
Li X, Yalaoui F, Amodeo L, Chehade H (2002) Metaheuristics and exact methods to solve a multiobjective parallel machines scheduling problem. J Intell Manuf 23(4):1179–1194CrossRef
27.
Brucker P, Sotskov YN (2007) Complexity of shop-scheduling problems with fixed number of jobs: a survey. Math Meth Oper Res 65:461–481MathSciNetMATHCrossRef
28.
Johnson DS, Aragon CR, Mageoch LA, Schevon C (1989) Optimization by simulated annealing: an experimental evaluation; part 1, graph partitioning. Oper Res 37:865–892MATHCrossRef
29.
Ghirardi M, Potts CN (2005) Makespan minimization for scheduling unrelated parallel machines: a recovering beam search approach. Eur J Oper Res 165(2):457–467MATHCrossRef
30.
Martello S, Soumis F, Toth P (1997) Exact and approximation algorithms for makespan minimization on unrelated parallel machines. Discrete Appl Math 75:169–188MathSciNetMATHCrossRef
31.
Allahverdi A, Ng CT, Cheng TCE, Kovalyov MY (2007) A survey of scheduling problems with setup times or costs, Eur J Oper Res
32.
Chen CL, Chen CL (2009) Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times. Int J Adv Manufact Technol 43(1-2):161–169CrossRef
33.
Tavakkoli-Moghaddam R, Mehdizadeh E (2007) A new ILP model for identical parallel-machine scheduling with family setup times minimizing the total weighted flow time by a genetic algorithm, IJE Transactions a: basics, vol 20(2)
34.
Pinedo ML (2008) Scheduling—theory, algorithms, and systems. Prentice–Hall, Englewood Cliffs
Metadata
Title
Complexity on Parallel Machine Scheduling: A Review
Author
D. K. Behera
Copyright Year
2012
Publisher
Springer India
Book
Emerging Trends in Science, Engineering and Technology

Print ISBN: 978-81-322-1006-1

Electronic ISBN: 978-81-322-1007-8

Copyright Year: 2012

DOI
https://doi.org/10.1007/978-81-322-1007-8_34

Premium Partners

    Image Credits