Operations Research · 1997 · 88 citations · 23 references
ManagementIndustrial EngineeringOperations ManagementProduction ControlProduction PlanningSchedulingJob SequencingJob Shop SchedulingMachine SchedulingProduction SchedulingScheduling TheoryCycle TimeCycle Time Optimization
This paper discusses the periodic job shop scheduling problem, a problem where an identical mixture of items, called a minimal part set (MPS), is repetitively produced. The performance and behavior of schedules are discussed. Two basic performance measures, cycle time and makespan, are shown to be closely related. The minimum cycle time is identified as a circuit measure in a directed graph. We establish that there exists a class of schedules that minimizes cycle time and repeats an identical timing pattern every MPS. An algorithm is developed to construct such schedules. We show that minimizing the makespan as a secondary criterion, minimizes several other performance measures. For makespan minimization, we examine earliest starting schedules where each operation starts as soon as possible. We characterize the cases where after a finite number of MPSs, the earliest starting schedule repeats an identical timing pattern every fixed number of MPSs. We also develop a modification to an earliest starting schedule that repeats an identical timing pattern every MPS when the beginning operations on the machines are delayed.
23
Network Flows: Theory, Algorithms, and Applications.
David K. Smith, Ravindra K. Ahuja, Thomas L. Magnanti et al. · Journal of the Operational Research Society · 1994 · 8.2K citations · Full text
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations
Robert W. Floyd · Communications of the ACM · 1962 · 4K citations · Full text
Stephen Warshall · Journal of the ACM · 1962 · 1.7K citations