Job-shop scheduling is almost always done in a batch modality. Jobs, routings, material and support resources for rouings, machines, operations, along with operation networks, delays, lags, etc are all fed into a scheduling engine and the schedule is generated. This is often referred to as the "paper tiger" approach and 'can' be useful in a job-shop. At least one can generate dispatch reports and try to follow them. I have used this type of system many times and have had good results. Especially useful for determining resource usage patterns and material requirments for known demand. Scenarios can be put through a "bake-off" and an course of action determined with relative confidence. The "batch" approach does, however, result in a production schedules that may be hard to actually achieve. As was mentioned, the real-world intercedes with "optimization" techniques.
Real-time scheduling brings together the algorithms of optimization with the infrastructure of information technology. This "always on" scheduling approach is ideal for job-shop environments. Coupled with "visibility" tools and monitoring technologies (OPC, historians, etc), these types of systems can offer valuable trending information for longer-term analysis while ensuring that production bottlenecks are addressed (TOC-style) and throughput maintained.
Of special note for the job-shop environment is the efficacy of "visibility" tools. Knowing that some job/process is going off-side ahead of time is invaluable in maintaining schedule compliance. The main problem here is that it requires a high degree of shop-floor discipline to ensure that feedback on production status is timely.
There are a variety of systems available today that can address your needs. Developing an algorithm is only part of the problem; creating a system that handles the real-world is a bigger problem.
Iain