Bounds for parallel machine scheduling with predefined parts of jobs and setup time

摘要

We examine a parallel machine scheduling problem with setup time in order to minimize the makespan. Each job consists of predefined parts, and the parts of a job can be processed concurrently in different machines. We first provide worst-case bounds of the Longest Processing Time and list schedules for special cases. We also develop a heuristic algorithm for scheduling parts of jobs with family setup time and propose its worst-case performance ratio. The application is the IoT-based smart factory with 3D printers as processing machines.