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

14 questions
Filter by
Sorted by
Tagged with
345 views

### Single machine job scheduling to minimize weighted sum of completion time

Given $n$ jobs, schedule them such that the weighted sum is minimum. weighted minimum sum S for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by : $S = \sum_{1\leqq i \leqq n} w_i C_i$ ...
5k views

### Getting parallel items in dependency resolution

I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
606 views

### Issues with using greedy algorithm (Interval scheduling variant)

I am trying to solve a problem of finding incompatible jobs set using greedy algorithm. However, I am not sure if greedy algorithm can solve this problem or I need to perform another approach. I have ...
282 views

### Ordering elements so that some elements don't come between others

Given an integer $n$ and set of triplets of distinct integers $$S \subseteq \{(i, j, k) \mid 1\le i,j,k \le n, i \neq j, j \neq k, i \neq k\},$$ find an algorithm which either finds a permutation $\pi$...
2k views

### Classification of job shop scheduling problems

I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory. The factory has several types of machines (say, ...
517 views

### Job scheduling with a bottleneck problem

Given $n$ jobs $J_1,J_2,...,J_n$, each job requires $T_i > 0, T_i \in N$ time to complete. Each job must be pre-processed and post-processed by a single machine M that can handle only 1 job at a ...
253 views

### Can Santa be both fair and efficient?

As the net-evergreen The Physics of Santa establishes, it is physically impossible for Santa to get a gift to every kid on the planet. Route planning won't help much there, but can a good planning ...
2k views

### Interval Scheduling Problem with Three Resources

So I am trying to figure out what kind of algorithm I would use if I wanted to implement the ISP with a predefined number of resources. Consider this example interval scheduling problem. Say there ...
2k views

### Find Minimum number of platforms

The questions is as follows with the answer: Q) Given the arrival and departure time of various trains in a station. Calculate the minimum number of platforms required such that no train has to ...
176 views

3k views

### Interval Scheduling Problem with more than One Resource

Consider the interval scheduling problem, see also here. In order to schedule the $n$ job requests over one resource, you sort the requests in order of finish time, choose the request with earliest ...