What kind of scheduling problem is this?

Question

I am trying to develop algorithm to solve following basic version of the problem. 1) I would like to know what this problem is called in literature so that I can look it up 2) What are efficient methods to solve this problem that I can look at

Please provide name of the methods/references if you can.

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. 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.

The goal is to schedule each job so that 1) you can reduce the cost of working overtime 2) reduce the fixed 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. This could be very standard problem in literature as I have seen similar problems solved for one day scheduling.

The difference between my problem and other problems is that, 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. I have gone through several articles but have not found anything that consider this additional penalty term for starting in a particular time slot.

Suppose schedule is defined by binary variable $X_{idtm}$ = 1 if job $i$ is assigned to machine $m$ on day $d$ and starts in time slot $t$, 0 otherwise. 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.

All jobs must be scheduled.

I have a formulation. I am trying to find if similar scheduling problems have been solved. What the problem is called, what are the algorithms used to solve such a problem.

Answer 1

Is there any specific route for each job or they can be performed on each machine when the machine is available?

In the first case, the problem can be interpreted as a job shop (or hybrid), other else you would formulate the problem as a resource-constrained project schedule. About the penalty/reward, as you mentioned, in the real application JIT (just in time) objective function is frequently used in the industry specifically in the APSs (Advanced Planning and scheduling software).

About the algorithms used to solve such a problem, you have many options.

• You can formulate the model as a mixed-integer program and solve it by using the appropriate software like CPLEX.
• If you are interested to use CP, you can check and find many examples to do that.
• Also, as excel is a basic software in the industry, there are excel-based optimization software like solverstudio which can be used to solve your problem.