INFOR Information Systems and Operational Research · 1991 · 44 citations · 0 references
ManagementIndustrial EngineeringOperations ManagementManufacturing ProcessesProduction PlanningSchedulingFlow Shop SchedulingJob SchedulingJob Shop SchedulingMachine SchedulingOpen Shop SchedulingScheduling TheoryHeuristic AlgorithmsJob Shop Scheduling Heuristics
We investigate the complexity of openshop scheduling problems. A number of variations of the shop with different objective functions have been surveyed. The problem of minimizing mean flow time in no-wait openshop as well as the problem of minimizing the number of late jobs for preemptive schedules are shown to be NP-hard An O(n log n) time algorithm for minimizing the total weighted number of late jobs in no-wait openshop is provided.