What kind of scheduling problem is this?

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.

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.
• No, there is no route for each job. They can be scheduled on any day, any time, any machine. There exist a symmetry which seems to be a problem. I have tried to solve this for 30 jobs, 3 machines, 5 days and 20 timeslots each day with Gurobi, which takes about 5 hours to solve. I do have symmetry breaking constraints that open the machines to use in order. Do you have any suggestions about how I can speed this up? Is Cplex better than Gurobi for such problems? May 17, 2020 at 14:41
• AFAIK, CPLEX and Gurobi are state-of-the-art solvers and you do not need to change them but, if you are interested to use CP, you could try CP optimizer embedded into CPLEX. About the solving time you mentioned, I think you will have to try reformulating your problem. While ago I tried to solve a machine scheduling problem in which was solved in more than 2 hours using a basic formulation but by using another formulation was solved in less than hour. May 17, 2020 at 17:25
• Also, if you have any issue about your problem formulation you could ask it on the community. :) May 17, 2020 at 17:37