3
$\begingroup$

There are $N - \{1 \ldots N\}$ jobs, each with processing time $p_j$, to be scheduled on $M - \{1 \ldots M\}$ machines over span of $D - \{1 \ldots D\}$ days and while working $T - \{1 \ldots E \ldots T\}$ hours at most each day. You can have factory working overtime after time period $E$ (5 pm), at extra cost but not after $T$. To use a machines, there is a fixed cost per day per machine. No cost is incurred if you choose not to use the machine. If the job is scheduled on a machine, there is a constraint to ensure that machine is used. There is a penalty / reward for starting the job $i$ at a particular time slot $t$ between $\{1 \ldots T\}$ on machine $m$, for each day $d$. Basically, there exist a penalty or reward cost for starting a job.

The goal is to schedule each job so that 1) you can reduce the cost of working overtime 2) reduce the fixed cost 3) You want to reduce penalty cost. Note that schedule specifies the job, the machine it is assigned to, time slot when it should start, and the day on which it should be scheduled.

$X_{idtm}$ = 1 if job $i$ is assigned to machine $m$ on day $d$ and starts in time slot $t$, 0 otherwise. $Q_{dm} \in \{0,1\}$ captures if machine is used or not each day. $C_f$ is fixed cost. $O_{dm} \in \{0,1\}$ captures if overtime was used in the machine.$C_o$ is overtime cost There is penalty term in addition to fixed machine cost and overtime cost, $(+ \alpha_{idtm} * X_{idtm})$ where $\alpha_{idtm}$ can be positive or negative. Note that $\alpha_{idtm}$ is a parameter. $Y_{idtm} \in \{0,1\}$ this variable keeps machine busy for $p_j$ duration from time t if job is started at time t.

The question is, as I increase the problem size, this model takes hours. I would like to know what my options are to speed things up.

1) I have one constraint to break symmetry to open machines in order as shown below (used by Denton et al.)

$Q_{dm} \geq Q_{dm'} \quad \forall m \in M, \qquad \forall m' > m \qquad \forall m' \in M, \qquad \forall d \in \delta $

2) I have constraint to not schedule jobs if it goes beyond time T, i.e. fixing some of $X_{idtm} = 0 $.

Here are few other questions,

1) What are other things that I am missing on? The model provides me solution fairly quickly if I am scheduling 10 jobs or so, how can I speed it up,

2) Is there any advantage of discretizing time slot as I have done with ${idtm}$.

If you can please point me to right references,

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.