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