In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I’m looking at scheduling problems in particular

In what cases is solving Binary Linear Program easy (i.e. P complexity)?

The reason I’m asking is to understand if I can reformulate a scheduling problem I’m currently working on in such a way to guarantee finding the global optimum within reasonable time, so any advice in that direction is most welcome.

I was under the impression that when solving a scheduling problem, where a variable value of 1 represents that a particular (timeslot x person) pair is part of the schedule, if the result contains non-integers, that means that there exist multiple valid schedules, and the result is a linear combination of such schedules; to obtain a valid integer solution, one simply needs to re-run the algorithm from the current solution, with an additional constraint for one of the real-valued variables equal to either 0 or 1.

Am I mistaken in this understanding? Is there a particular subset of (scheduling) problems where this would be a valid strategy? Any papers / textbook chapter suggestions are most welcome also.

Scheduling jobs online on 3 identical machines – a lower bound of 5/3

Consider the Online Scheduling Problem with $ 3$ identical machines. Jobs, with arbitrary size, arrive online one after another and need to be scheduled on one of the $ 3$ machines without ever moving them again.

How can I show, that there can’t be any deterministic Online-Algorithm which achieves a competitive ratio of $ c<\frac{5}{3}$ .

This should be solved by just giving some instance $ \sigma$ and arguing that no det. algorithm can do better. Same can easily be done for $ 2$ machines and $ c<\frac{3}{2}$ . Sadly I can’t find any solution to this (more or less) textbook answer.

Why is the Greedy Algorithm for Online Scheduling on uniform machines NOT competitive?

Consider the Online Scheduling Problem with m machines and different speeds.

Each instance $ \sigma$ consists of a sequence of jobs with different sizes $ j_i\in\mathbb{R^+}$ . At each step in time any algorithm gets to know the one new job of $ \sigma$ which needs to be assigned to one machine. The goal is to minimize the makespan (by the end of the online sequence \sigma$ ).

I want to find an instance such that the Greedy Algorithm, which assigns each new job to the machine which finishes it first, is only $ \Theta(\log m)$ -competitive.

Any ideas? I can’t find any articles regarding my problem.

Greedy sequential/parallel task scheduling

We have N tasks that need to be scheduled for processing. Each task consists of two parts that need to executed in order. The first one is guarded by a mutex and therefore only one task can be executing this part at a time. The second part has no such constraint and any number of the tasks can be executing this at the same time. For task i we know how much time it needs to spend in each part, namely mi for the guarded part, and ai for the part that can be executed in parallel.

The problem is to find a permutation of the tasks such that the time needed to execute all of them is minimized.

My intuition says that this can be solved with a greedy algorithm, by scheduling the tasks in descending ai order.

For example given the tasks with:
m1 = 3, a1 = 9
m2 = 2, a2 = 7
m3 = 6, a3 = 10

The optimal solution is the permutation 3, 1, 2.

However, I have trouble proving that the greedy solution is optimal. Any ideas on how to do that?

Understanding proofs Lemma 11 & 10 in this specific Computer Science Scheduling Paper

I’m having a hard time wrapping my head around the proofs Lemma 11 and Lemma 10 (Pages 10 and 11) in this paper called: Preemptive and Non-Preemptive Real-Time UniProcessor Scheduling.

Generally the proofs have very few steps in between and I can’t seem to understand how the author continues from one step to another. Therefore, I would be very gratefull in a more step by step detailed explanation of the proofs mentioned.

Thank you in advance!

Three City Scheduling

I came across the following interview question

There are 2N people a company is planning to interview. The cost of flying the i-th person to city A is costs[i][0], and the cost of flying the i-th person to city B is costs[i][1].

Return the minimum cost to fly every person to a city such that exactly N people arrive in each city.

The solution to this involves greedy approach, where we sort the array based on the “profit” parameter. profit of choosing city A for a candidate i is defined as costs[i][1] - costs[i][0] and choose the top half elements from the sorted array to go to A and rest to B.

What if this question is modified to 3 cities and you have find optimal partition of n/3 chunks? Will greedy algorithm still work?

Scheduling method for guest network in TPlink (TD-W8960N) ADSL modem [closed]

I have the ADSL modem like this: enter image description here

and i want to have one time scheduled sharing internet, but the TPlink page not have the time schedule as you can see here:

enter image description here

I have tried this upgrade file but no change in the guest network options.

And see the page of TPlink site which said Archer D2 and TD-W9980(B) have this option,

I was thinking to find some auto web scraping script to automatically open the guest network setting page on my modem page and tick this option in the modem every day, but i have doubt which, this work have bad effect on the modem and maybe this action reset it every day and damage it!.

So what methods do you suggest to do this?

Thanks.

Need help to understand the math behind the logic for scheduling problem using Reinforcement Learning

I am working on a problem for scheduling VMs considering efficient resource and energy utilisation and I came across this paper. I understand RL and how Q-Learning works which they are trying to use in paper. However, I am not able to achieve an intuitive understanding of the algorithm suggested (page 3).

I understand that equal importance has been given to utilisation and power consumption but with reverse, let’s say signs. But Step-3 is not intuitive. Can someone help me get a better understanding of the same algorithm?

Scheduling of process manufacturing with setup times


Overview

The process manufacturing is (in contrast to discrete manufacturing) focused on the production of continuous goods such as oil. The planning is typically solvable by means of Linear Programming, come constraints can be introduced for MILP.

Problem Formulation

The problem consists of

  • Sequence of consecutive time intervals $ t\in\{1,\dots,n_t\}$ , each with start and end $ (s_t,e_t)$ and length $ l_t=e_t-s_t$ . Consecutive means $ e_{t}=s_{t+1}$ for all $ t\in\{1,\dots,n_t-1\}$ .
  • List of type of goods that are being produced: $ j\in \{1,…,n_j\}$
  • Demand of each type of good per time interval $ d_{j,t}$ .
  • List of production lines $ i\in{1,\dots,n_i}$
  • Availability of production lines per time interval $ a_{i,t}$ . $ a_{i,t}$ is binary – whether available or not.
  • Manufacturing speed per production line per type goods $ v_{i,j}$ .
  • Setup time of production line from one type of goods to another one $ u_{i,j,j’}$ .
  • Price for using a production line (leasing based), counted per minute $ c_{i}$

The goal is to plan the production lines so the demand is covered and the price for leasing is minimal.

Notes:

  • The setup time can be shorter or longer or equal to the length of the intervals
  • It is acceptable that the production line will not work the whole time interval if the supply has been completed sooner
  • The setup to the production of another good can start any time, not necessarily at the beginning of an interval.

Example

There are two production lines, i.e., $ n_i = 2$ and there are two types of goods, i.e. $ n_j=2$ .

We have two intervals, i.e. $ n_t=2$ , each has a leght of 1 hour. Say one starts at 1 pm, the second at 2 pm.

The demand is:

  • $ d_{1,1}=1.1$
  • $ d_{1,2}=1$
  • $ d_{2,1}=0.5$
  • $ d_{2,2}=1$

The of running the production lines are:

  • $ c_{1} =c_{2} = 1$ USD/minute

All possible setup times are twelve minutes, i.e.:

  • $ u_{i,j,j’}=0.2$ for all $ i,j,j’$ where $ j\neq j’$ .

The speeds are:

  • $ v_{1,1}=1.1$
  • $ v_{1,2}=1.5$
  • $ v_{1,1}=1$
  • $ v_{1,1}=1$

Obviously, the demand is met for a total cost of $ 4$ if the first line is producing the first type of goods at both intervals and the second line is producing the second type.

However, it might be tempting to switch them after the first interval. If there would be no setup time needed, the cost would be $ 1+1+1+0.5/1.5=3.33$ which is better. However, this is not possible because of the setup time of the second production line.

Question

What is the algorithm to schedule this manufacturing process optimally?

An answer is welcome even if it would outline the way and approach (MILP, SAT, CSP,…).

Ideas fo far

  • If the length of intervals would be fixed, say 1 hour and the setup time would be defined in terms of these units, say 2 hours. Then, it might be solvable by SAT/CSP.
  • An idea is to use an evolutionary algorithm that would: consist of a sequence of activities with mutations (add an activity, delete activity, prolong activity) and crossover (mix two plans in a random way).