Given a set of $N$ jobs and two machines A and B, each machine can process only one job at a time. Each job, if processed, must be processed by machine A before processed by machine B. The processing time of job $i$ at machine A and B is $t_{i}^{A}$ and $t_{i}^{B}$ respectively. The deadline and the profit of job $i$ are $d_i$ and $p_i$ respectively. All jobs are available at time 0.

Problem: find a job scheduling that maximizes the total profit.

This problem is a reformulation of a small problem I face in my research. I know the job scheduling with deadline problem, but my problem is different. I am not a computer scientist, so any suggestions about how to solve my problem would be very helpful.

  • $\begingroup$ I'd try dynamic programming. There are lots of tutorials and discussions around the 'net on it and on job scheduling. $\endgroup$ – vonbrand Jan 22 '16 at 13:12
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We do not want to just do your (home-)work for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? You may also want to check out our reference questions. $\endgroup$ – Raphael Jan 22 '16 at 13:13
  • $\begingroup$ The above problem is a reformulation of a small problem I face in my research in different field, but it is not the focus of my research. I know only the job scheduling with deadline problem but not the above one. I think it is well-known and already solved. What I want to obtain when asking here is the name / approach to solve it. $\endgroup$ – novatena Jan 22 '16 at 13:29
  • $\begingroup$ I suggest you try out a number of small examples (problem instances), find the optimal solution for each, see if you can spot any patterns that seem like they might be useful, and then try to prove or disprove each conjectured pattern. Conjecture: it suffices to consider only schedules where, immediately after a job finishes at machine A, it immediately starts at machine B (i.e., there exists an optimal solution where this holds for all processed jobs). Can you prove or disprove this conjecture? If the conjecture holds, the problem becomes a standard job scheduling problem. $\endgroup$ – D.W. Jan 22 '16 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.