Scheduling with families of jobs and delivery coordination under job availability

We consider in this paper the scheduling of families of jobs in which both processing and delivery are coordinated together. Only one vehicle is available to deliver the jobs to specified customers. The jobs can be processed together to form processing batches on the machine and setups of batches are required when the machine is changing from one family to another. Jobs from different families cannot be transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We propose an O(nlogn)-time optimal algorithm for the scheduling problem under the group technology assumption. For the scheduling problem without the group technology assumption, we show that the problem is NP-hard and give an O(f2nf)-time dynamic programming algorithm, where n is the number of jobs, and f is the number of families; we also provide a heuristic algorithm with a performance ratio of 3/2.