Fast LP models and algorithms for identical jobs on uniform parallel machines

作者：Lin Yang Kuei^*

来源：Applied Mathematical Modelling, 2013, 37(5): 3436-3448.

DOI：10.1016/j.apm.2012.07.023

• Scheduling
• Identical jobs
• Uniform parallel machines
• Linear programming
• Algorithm

Scheduling n identical jobs on m uniform parallel machines to minimize scheduling work is very common in practice. The case of identical jobs is common in manufacturing systems, in which many products have identical designs or processing times on the same machine. Factories often buy new equipment but retain their slower, older equipment; this results in machines having different processing speeds.
This research proposes several linear programming (LP) models and algorithms for identical jobs on uniform parallel machines for individual minimization of several different performance measures. We also consider an extension of this problem in which a learning effect is present. The proposed LP models can find optimal schedules for identical jobs on uniform parallel machines. Also, the proposed LP models provide structure insights of the studied problems and provide an easy way to tackle the scheduling problems. Developers of mathematical programming models for other extensions of scheduling problems with identical jobs on uniform parallel machines might benefit from our models. The algorithms proposed here can find optimal solutions with the speed and efficiency necessary to meet real world requirements.

• 出版日期2013-3-1