8
$\begingroup$

I am currently working on software that deals with a specific type of scheduling problem, and I want to improve the scheduling algorithms that it uses.

However, when I tried to research algorithms the information I found deals mostly with a much different kind of scheduling problem.

In my problem, the givens are:

  • A set of $J$ jobs. Each job $j$ has an availability interval with start and end times $[s_j,e_j]$.
  • A reward function $R(j,t)$ which gives the utility of processing a job for a given amount of time.
  • A changeover time function $C(j,j',t)$ which gives the amount of time required, starting at a time $t$, to switch from job $j$ to job $j'$.
  • A set of $M$ minimum time constraints. Each constraint $m$ has an associated set of jobs $J_m$ and a minimum time $c_m$.

The solution is a list of jobs and intervals: $\{(j_1,I_1),(j_2,I_2),\ldots,(j_N,I_N)\}$.

The constraints are:

  • Each interval must fall within the corresponding job's availability interval: $I_n\subseteq[s_{j_n},e_{j_n}]$.
  • There must be adequate changeover time between jobs: $$\max I_n + C(j_{n},j_{n+1},\max I_n)\leq \min I_{n+1}$$
  • The minimum time constraints must be met: $$\sum_{\substack{n=1 \\ j_n\in J_m}}^{N}\left|I_n\right|\ge c_m $$

The objectives are (multiobjective optimization):

  • (Primary) Maximize the reward given by: $$\sum_{n=1}^{N}R(j_n,\left|I_n\right|)$$
  • (Secondary) Minimize the amount of "idle" time (idle time is the "slack" in the changeover constraint): $$\sum_{n=1}^{N-1}\left(\min I_{n+1}-\max I_n\right) - C(j_{n},j_{n+1},\max I_n)$$
  • (Secondary) Minimize the longest idle (same as previous with $\max$ replacing $\sum$).

Has this type of problem been studied? If so, what names is it usually called by?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ this actually sounds very much like a (fractional) knapsack problem and may thus be easy to solve via a greedy algorithm or linear programming. $\endgroup$
    – Marco Lübbecke
    Jul 19, 2019 at 4:27
  • $\begingroup$ Is time in your problem continuous or discrete? For the discrete case, this problem might just be a shortest path problem (unless you have additional constraints). $\endgroup$
    – PSLP
    Jul 19, 2019 at 10:58
  • 1
    $\begingroup$ How do you consider a job done? You said that it's allowed to process only a part of a job. This might complicate everything. Also, I think your example of attending a conference is not a very good one. In that case, everything is scheduled beforehand, and you have to select which talks to attend. In general scheduling problems, you define the order of processing jobs. $\endgroup$
    – Ehsan
    Jul 19, 2019 at 19:23
  • $\begingroup$ @Ehsan 1) A score or weight is awarded in proportion to the amount of the job processed, so there is not really a sense of "completion" for a job. 2) In my case, the jobs are scheduled beforehand and I have to choose which jobs to process; this is what makes it different from a "general scheduling problem." I don't know what to call this other than a scheduling problem though. $\endgroup$
    – 2012rcampion
    Jul 19, 2019 at 20:09
  • 1
    $\begingroup$ @Luke The problem is nominally continuous, but discretizable; the original algorithm I am trying to improve upon discretizes the intervals into 20-second increments (for reference, we typically schedule a week at a time, so that's around 30k timesteps). I in fact am trying a shortest-path/dynamic programming approach; the issue is that, as you identified, it's more difficult to implement global constraints with this approach (e.g. a typical constraint is that a particular subset of jobs must have at least 10,000 seconds of time processed in total). $\endgroup$
    – 2012rcampion
    Jul 19, 2019 at 20:17

2 Answers 2

Reset to default
6
$\begingroup$

I guess I'm missing something here, or making an incorrect assumption, because the problem seems trivial. I'm assuming that the contribution of each partially done project is a nondecreasing function of the time spent on it, that contributions are additive (the value of partially doing task 1 does not in any way depend on what is done with task 2), that the worker does not fatigue (so worker time late in the shift is no different from worker time early in the shift), and that there is no cost in time or objective value for moving from one task to another. Under those assumptions, you can determine from the data which tasks are available at any instant and time and which among them has the highest object contribution rate per unit time. The contribution-maximizing solution is just to have the worker, at every time epoch, work on whichever task has the highest contribution rate among those available at that epoch.

Is there something else in play here?

Improve this answer
$\endgroup$
1
  • $\begingroup$ The problem has both local constraints (e.g. it takes a non-negligible time to switch tasks) and global constraints (e.g. there are groups of jobs that require a minimum total processing time). I will update the question with a more complete description of the problem. $\endgroup$
    – 2012rcampion
    Jul 22, 2019 at 2:03
4
$\begingroup$

Take visiting a conference as an example; you (the worker) want to choose which talks/events (jobs) to attend (process) during the fixed duration of the conference, but can only be in one place at once. Has this type of problem been studied? If so, what names is it usually called by?

Generally it's called scheduling, timetabling or rostering, but there are many specific variations.

Such problems go by various names (all the following information is from Wikipedia):

  • Generalized Assignment Problem (more than one person and one task)

    There are a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost and profit that may vary depending on the agent-task assignment. Moreover, each agent has a budget and the sum of the costs of tasks assigned to it cannot exceed this budget. It is required to find an assignment in which all agents do not exceed their budget and total profit of the assignment is maximized.

    In the special case in which all the agents' budgets and all tasks' costs are equal to 1, this problem reduces to the assignment problem. When the costs and profits of all tasks do not vary between different agents, this problem reduces to the multiple knapsack problem. If there is a single agent, then, this problem reduces to the knapsack problem.

  • Assignment Problem

    If the numbers of agents and tasks are equal, and the total cost of the assignment for all tasks is equal to the sum of the costs for each agent (or the sum of the costs for each task, which is the same thing in this case), then the problem is called the linear assignment problem. Commonly, when speaking of the assignment problem without any additional qualification, then the linear assignment problem is meant.

  • Nurse Scheduling Problem (NSP), also called the nurse rostering problem (NRP)

    The operations research problem of finding an optimal way to assign nurses to shifts, typically with a set of hard constraints which all valid solutions must follow, and a set of soft constraints which define the relative quality of valid solutions. Solutions to the nurse scheduling problem can be applied to constrained scheduling problems in other fields.

  • Workplace Scheduling

    A schedule, often called a rota or roster, is a list of employees, and associated information e.g. location, working times, responsibilities for a given time period e.g. week, month or sports season.

    A schedule is necessary for the day-to-day operation of many businesses e.g. retail store, manufacturing facility and some offices. The process of creating a schedule is called scheduling. An effective workplace schedule balances the needs of stakeholders such as management, employees and customers.

  • Gantt Chart

    A Gantt chart is a type of bar chart that illustrates a project schedule, named after its inventor, Henry Gantt (1861–1919), who designed such a chart around the years 1910–1915. Modern Gantt charts also show the dependency relationships between activities and current schedule status.

    This chart lists the tasks to be performed on the vertical axis, and time intervals on the horizontal axis. The width of the horizontal bars in the graph shows the duration of each activity. Gantt charts illustrate the start and finish dates of the terminal elements and summary elements of a project. Terminal elements and summary elements constitute the work breakdown structure of the project. Modern Gantt charts also show the dependency (i.e., precedence network) relationships between activities.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I don't think this fits an assignment problem, since in such a problem all tasks must be assigned an agent, of which there are many. I have only one agent so most tasks cannot be assigned. The Gantt Chart is a way of visualizing solutions to the regular version of the scheduling problem, so it's not applicable either. $\endgroup$
    – 2012rcampion
    Jul 22, 2019 at 2:07
  • 1
    $\begingroup$ @2012rcampion This answer includes single and multiple persons, tasks, days, scheduling - it includes what you asked for and expands upon it for future viewers. Many of the links include the mathematics behind the algorithms and permit scaling down to a single person. Visualization of the output was included as it shows how the results are traditionally presented. $\endgroup$
    – Rob
    Jul 22, 2019 at 3:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.