  We propose three novel mathematical optimization formulations that solve the
same two-type heterogeneous multiprocessor scheduling problem for a real-time
taskset with hard constraints. Our formulations are based on a global
scheduling scheme and a fluid model. The first formulation is a mixed-integer
nonlinear program, since the scheduling problem is intuitively considered as an
assignment problem. However, by changing the scheduling problem to first
determine a task workload partition and then to find the execution order of all
tasks, the computation time can be significantly reduced. Specifically, the
workload partitioning problem can be formulated as a continuous nonlinear
program for a system with continuous operating frequency, and as a continuous
linear program for a practical system with a discrete speed level set. The task
ordering problem can be solved by an algorithm with a complexity that is linear
in the total number of tasks. The work is evaluated against existing global
energy/feasibility optimal workload allocation formulations. The results
illustrate that our algorithms are both feasibility optimal and energy optimal
for both implicit and constrained deadline tasksets. Specifically, our
algorithm can achieve up to 40% energy saving for some simulated tasksets with
constrained deadlines. The benefit of our formulation compared with existing
work is that our algorithms can solve a more general class of scheduling
problems due to incorporating a scheduling dynamic model in the formulations
and allowing for a time-varying speed profile. Moreover, our algorithms can be
applied to both online and offline scheduling schemes.
