What dispatching rule minimizes average cycle time for a deterministic single machine? What rule minimizes maximum tardiness? How can one easily check to see if a schedule exists for which there are no tardy jobs?

Question: Explain the dispatching rules that can minimize the average cycle time and maximum tardiness for a deterministic single machine, and describe a method to check if there is a schedule with no tardy jobs. Answer: The shortest processing time (SPT) dispatching rule minimizes the average cycle time in a deterministic single machine, where jobs are processed in the order of their increasing processing times. To minimize maximum tardiness, the Earliest Due Date (EDD) dispatching rule should be used, in which jobs are processed according to their due dates in ascending order. To check for a schedule with no tardy jobs, Moore's Algorithm can be used, which involves ordering the jobs by their due dates, initializing an empty set, and adding jobs to the set while testing for tardiness and adjusting accordingly. If there are no tardy jobs in the final schedule, it indicates the existence of a schedule with no tardy jobs.