Author(s)

Zhan Yong ¹, Zhong Yuguang ¹

Affiliation(s)

¹ College of Mechanical and Electrical, Harbin Engineering University, Harbin, 150001, China

Corresponding Author

Zhan Yong

ABSTRACT

This paper addresses the scheduling problem of parallel machines with machine eligibility restrictions and special jobs with the objective of minimizing the makespan. Each job can only be assigned to a specific subset of the machines. And the processing times of jobs are restricted to one of two values, 1 andε. A semi-matching model G=[J∪M,E,W] is presented to formulate this scheduling problem. We propose an approximation algorithm, which is composed of two steps, that is, initial solution construction and initial solution improvement. The initial solution construction algorithm is developed to build a feasible solution by performing a simple greedy heuristic method. The initial solution is used as a starting point by the improvement algorithm. The main idea of the improvement algorithm is to construct alternating tree, then to find the optimal alternating path for each vertex in M iteratively. In order to improve efficiency, the length of each path in alternating tree is limited to 4 at most. 

KEYWORDS

parallel machine, machine eligibility restrictions, approximation algorithm

CITE THIS PAPER

Yong, Z. and Yuguang, Z. (2016) Approximation Algorithm for Scheduling Parallel Machines with Machine Eligibility Restrictions and special jobs. Journal of Engineering Mechanics and Machinery (2016) 1: 28-33.

REFERENCES

[1] PURUSHOTHAMAN D, MARIO C V: Expert Systems with Applications Vol. 39(1) (2012), p.1451
[2] WANG W L, WANG H Y, ZHAO Y W , ZHANG L P, XU X L: Computers & Operations Research Vol.40(5) (2013), p.1196
[3] TAN Z Y, CHEN Y, ZHANG A: International Journal of Production Economics Vol.146(1) (2013),  p.293
[4] LIU M, ZHENG F F, WANG S J, XU Y F: Theoretical Computer Science Vol.497(29) (2013), p.108
[5] LOW C P: Information Processing LettersVol.100(4) (2006), p.154
[6] DORATHA E D, STEFAN H: Lecture Notes in Computer Science Vol.2647 (2003), p.107.

Sponsors, Associates, and Links

---

• Cybernetics and Mechatronics
  
  
• Digital Manufacturing and Process Management
  
  
• Ultra-Precision Machining Process
  
  
• Journal of Robotics and Biomimetics
  
  
• Prognostics, Diagnostics and Health Management
  
  
• Micro-Electro-Mechanical Systems
  
  
• Journal of Precision Instrument and Machinery
  
  
• Engineering and Solid Mechanics
  
  
• Fracture and Damage Mechanics
  
  
• Frontiers in Tribology
  
  
• Fluid and Power Machinery
  
  
• Chemical Process Equipment
  
  
• Journal of Assembly and Manufacturing
  
  
• Mechanical Vibration and Noise