Questions tagged [scheduling]
Questions about the optimisation problem of ordering a set of tasks so that some objective function (e.g. makespan) is minimised. The set of constraints is crucial; in particular, there is a large body of research covering online variants. Use the process-scheduling tag for questions specifically about scheduling in operating systems.
285 questions
- Bountied 0
- Unanswered
- Frequent
- Score
- Trending
- Week
- Month
- Unanswered (my tags)
0
votes
1
answer
43
views
Scheduling Training for Two Dogs with Rest Constraints
You are a dog trainer tasked with training two dogs, Peter and Markley, for train1 days and train2 days, respectively. You can ...
1
vote
1
answer
73
views
Complexity of determining feasibilty of a generalization of the interval scheduling problem
Consider the following generalization of the interval scheduling problem:
We have a set of groups, each group is specified by a set of disjoint time intervals. Unlike the group interval scheduling ...
1
vote
1
answer
77
views
Finding the minimum cost at each point in time from a set of weighted intervals
Lets say we have a list of intervals that also has a value associated with it. Assume that there is always atleast on interval active.
The solution would be a timeline of non overlapping intervals ...
0
votes
1
answer
62
views
Cruiseship Scheduling Problem
I was asked to help build a code that solves a "cruiseship scheduling problem".
A cruiseship has a number of guests. Guests can select/book several land excursions and workshops. The cruise ...
0
votes
0
answers
50
views
Input Example for Load Balancing: Greedy vs Ordered Scheduling Algorithm
I'm working on a problem involving load balancing across three machines. I need to find an input example (a list of job sizes) where the greedy scheduling algorithm produces a strictly lower makespan ...
1
vote
0
answers
67
views
Considering that we have the LPT greedy algorithm for the partition problem, do we need PTAS's or FPTAS's in practice?
I was reading these notes on approximation algorithms and I stumbled across a PTAS for an optimization version of the partition problem (essentially the Identical-machines scheduling $P_2 \|C_{\...
0
votes
1
answer
88
views
Complexity of Scheduling n Tasks on m Machines with Identical Execution Times, Dependencies, and Time Lags
This is a scheduling problem with $n$ tasks across $m$ machines. Tasks have dependencies (DAG) and can be divided into two types: A) need resources $R$ and have an identical execution time. B) do not ...
0
votes
2
answers
198
views
Greedy solution for minimum weight where all tasks are allocated
I'm trying to solve exercise 13 from Chapter 04 of Algorithms Design (Eva Tardos) books. The problem is the following:
The way I solved: was to have a greedy solution, where I always choose, for an i,...
0
votes
0
answers
291
views
Interval scheduling; sort by ending times
You have $n$ events on your calendar, defined as intervals with a start time $s_i$ and a finish time $f_i$.
The events might overlap, and you want to attend all the events, so you are going to create $k$...
1
vote
1
answer
73
views
Iteration scheduling vs processor scheduling
In parallel programming the iteration scheduling is defined as the determination of the logical execution time for each loop iteration, while in operating systems, the processor scheduling (FCFS etc) ...
1
vote
1
answer
51
views
Schduling theory with weekends and holidays
My wife has a small workshop where she fixes dolls.
She works alone without any external help.
She has N orders from her clients, she estimates each order and she has deadline for each order.
She ...
0
votes
1
answer
216
views
3 Processor Scheduling
A set of n independent tasks, each having integer execution times,
are to be executed using three identical processors. A task can be
executed in any of the three processors. Develop a sequential
...
1
vote
1
answer
108
views
Round-robin tournament scheduling, with teams that may share their home field
I need to implement an algorithm to create schedules for round-robin tournaments (where each team faces each other team exactly once), but with the constraint that up to 2 teams – that may play in ...
1
vote
1
answer
1k
views
Showing this scheduling problem is NP-hard
I've been reading up on scheduling problems and the class of them that is NP-complete. Specifically, this is a foundational text on such problems, but the reductions are not clear to me. Can someone ...
user avatar
user163952
0
votes
1
answer
167
views
Should I use linear programming for my timetable generator?
I am creating a timetabling software for a school, which given parameters for teachers/class sizes will output a timetable. There will be a list of classrooms per subject and a list of teachers per ...