# What kind of scheduling problem is this?

I'm working on a problem and would like to do some research on similar problems to help refine my approach. Can anyone help me identify what kind of problem this is or, at least, what kind of problems it relates to?

The basic model is a set of different job types, handled by a set of machines. There is also a dispatcher that carries parts between machines. I have estimates for the travel times involved when using a dispatcher to perform transfers and I also have estimates for the amount of time required that each job type takes to execute. The exact process flow between job types is dynamic (i.e. if there are $A$, $B$ and $C$ jobs, the result of $A$ can determine whether it gets routed to either $B$ or $C$.) New parts can arrive in the system and parts will eventually be routed out of the system after a job completes.

So, in summary:

Setup: Finite set of job types ($J_1, J_2, J_3, ..., J_n$) and machines to execute them ($M_1, M_2, M_3, ..., M_m$); a given job type might have multiple machines that support it. We can designate $M_{INPUT}$ as a special 'input machine' which can hold multiple parts that are available to be brought in to the system.

Inputs: A set of parts arrive over time at $M_{INPUT}$, where the arrival time can be denoted as $T_i$ and they are each assigned a sequence of jobs to perform $S_i$, though the algorithm cannot know the exact sequence in advance.

Process:

The dispatcher can take one of two actions at any given time:

1. Decide to move between two machines, where the time to transfer is a known $\tau(M_{i_1},M_{i_2})$.
2. Decide to exchange the part it currently holds with the part in the machine it is at. This exchange takes a fixed time $\tau_E$.

Every job type takes a known time $D_k$. After a given job at a particular machine completes, it assigns the next job in its sequence $S_i$. If the sequence is exhausted, it is routed to a special machine $M_{OUT}$ for routing out of the system.

Problem: Scheduler algorithm has to produce a series of dispatch orders (either move or exchange operations) to push parts through their job sequences and ultimately out of the system. The optimization criterion is to be capable of handling aggressive input sequences (more parts, more often), and maximize the number of parts finally moved through $M_{OUT}$ over the execution time of the system.

I believe this is a type of scheduling problem (sounds somewhat similar to Job Shop Scheduling?) I'm currently approaching this by considering different orderings of upcoming transfers in a branching fashion, generating an estimated timeline up to a certain limit forward in time, then preferring the schedules that move the most parts in the least amount of time. I'm pretty sure this kind of problem has been studied more rigorously, however and would like to learn more about the theory behind it.

• not sure. But close to or some generalisation of job shop scheduling. – Kalle Sep 1 '14 at 9:11
• – Nikos M. Sep 4 '14 at 3:33
• you might also be interested in multi-criteria scheduling – Nikos M. Sep 4 '14 at 3:39