Machine scheduling problems with position-dependent availability constraints

Abstract

Machine scheduling problems can be found in any practical environment from logistics to manufacturing, where tasks, called jobs, are completed by assigning them to resources, called machines. In this thesis, we assume that the execution of jobs deteriorates the machine to the point where it may not be in a state to process further jobs, or, more generally, restricts the availability of the machine. Time is often considered to be the main factor in machine deterioration, such as the time elapsed since the start of planning. However, with regard to practice, there are other important factors besides time that can have a significant impact on the machine state. In this work, we concentrate on factors based on the job positions in the scheduling sequence, summarized as position-dependent machine availability constraints. This characteristic can be found in any production or logistics environment where the assignment of the job to the machine determines the availability of the machine to process jobs, rather than the processing time. First, a definition and the existing literature of the superordinate research field of problems with position-dependent availability is given: state-dependent machine availability. In the following, single machine scheduling problems with position-dependent maintenance or with jobs that have to be sequenced at fixed positions are analyzed regarding their complexity. These assumptions represent specific characteristics of position-dependent availability in scheduling. For each assumption, complexity results are presented for single machine scheduling problems minimizing completion time or due date related objective functions. In addition, polynomial-time algorithms are formulated for specific scheduling problems. Finally, we deal with the hybrid flow shop scheduling (HFS) problem that is characterized by a flow shop layout with at least one stage of processing with parallel machines. Priority rules and constructive heuristics are tested and evaluated on 1260 instances for the two-stage no-wait HFS problem with two identical machines on the first stage and one machine on the second stage, which is known to be NP-hard. Furthermore, HFS problems with unrelated machines are assumed, considering setup times on the machines caused by different job families. Constructive heuristics are tested on 960 instances to study the influence of the number of setups on the results for completion time related objective functions.