We consider a parallel machine scheduling problem, where the inputs are a set of jobs J =
{J1, ..., Jn} with release dates r1, . . . , rn and a set of machines M = {P1, ..., Pm}, and the
output is a schedule which assigns each task Ji to a machine Pk, and indicates its starting date
Si. The time that machine Pk needs in order to process job Ji is denoted by pi,k. Each job Ji
has to me scheduled by one machine out of a set Mi ⊆ M. One of the important variants is
uniform-machine scheduling. In this problem, some machines are uniformly faster than others
in processing each job. This means that each machine has a speed factor vk which impacts the
run time of a job Ji on it, given a nominal job duration pi , as follows: pi,k = pi/vk.
In the context of electronic manufacturing, and especially Surface-Mount technology (SMT),
plants have automated and continuous production lines, (identified here to machines) which
operate 24-7. These lines follow complex processes, in which each PCB (printed circuit board)
undergoes many transformations through several steps. The production process goes generally
through 4 big phases : Front-End, ICT(In-Circuit Testing), Back-end and Packaging. In the
present work, we're interested in Front-end, which consists in assembling electronic devices
on a PCB board via SMT placement machines. More precisely, during front-end, each PCB
has 2 jobs to execute, mounting devices on its 1st face and mounting devices on its 2nd
face. This yields a precedence constraint between the 2 jobs. Consequently, the static and
deterministic form of our problem problem is a strongly NP-hard uniform-machine scheduling
problem denoted Q|ri, Mi, si,j,k, prec| ∑ wiTi in the standard 3-field notation for scheduling.
Setup time si,j,k is a delay needed before starting a new job Jj on a machine Pk, knowing that
we had a job Ji processed before on the same machine.
In practice, the line speed varies over time, and can be defined as a stochastic function of
time. For a particular scenario vk(t), if a task is assigned to line k, its start time Si and its
completion time Ci satisfy ∫ t=Ci
t=Si vk(t)dt = pi .