Solution techniques for the blocking job shop scheduling problem with total tardiness minimization

Abstract

Planning the course of events and activities constitutes an everyday challenge in many companies. Complex decisions are to be made regarding the allocation of a diverse range of resources and the corresponding processing sequences of tasks. Especially in the manufacturing of highly customized goods and the operation of cost-intensive logistics systems, efficient schedules have an enormous effect on the long-term success of an enterprise. Therefore, the ambitious idea of a reliable decision support for human planners is pursued by researchers in scheduling theory for many decades. While several classical scheduling problems are well studied, the integration of real-world constraints and objectives shows a lack of theoretical understanding. In order to provide a profound study in this research direction, a practically relevant class of job shop scheduling problems is comprehensively investigated with regard to the boundaries of exact solvability by mixed-integer programming techniques, the applicability of well-known heuristic methods and the advantageousness of hybrid matheuristic approaches. The job shop scheduling problem is known as a combinatorial optimization problem of considerable intricacy, for which even simple variants are proven to be strongly NP-hard. A set of jobs is required to be handled by a set of machines, where every job features an individual technological route of processing. A single processing step of a job is denoted as an operation, which is defined by a designated machine and processing time. In order to implement real-world conditions, a release date is given for every job and the recirculation of jobs is allowed. The absence of intermediate buffers in the planning situation is considered as a special circumstance, for instance, occurring in the production of huge items, in robotic storage frameworks and in railbound logistics systems. A schedule is to be determined, which assigns certain periods of working time of the required machines to the operations of each job, so that the given restrictions are met. Motivated by an ever-growing need to generate reliable schedules and increase customer satisfaction, the minimization of the total tardiness of all jobs is examined as an optimization criterion of practical relevance. For the purposes of providing a detailed structural description of the problem under study, on the one hand, and detecting the current boundaries of exact solvability, on the other hand, the blocking job shop scheduling problem with total tardiness minimization (BJSPT) is comparatively modeled by two mathematical formulations. Significantly smaller numbers of required variables and constraints in the optimization program can be reported for one type of sequence-defining variables in contrast to the other. In line with this observation, the computational results obtained by a state-of-the-art mixed-integer programming solver clearly indicate the advantages of the usage of binary ordering variables for all pairs of operations of different jobs requiring the same machine. Furthermore, the experiments show that the capability of exact general-purpose solution techniques do not meet the practical conditions in solvable problem size, solution quality and runtime. Additionally, several instance key measures are proposed in order to characterize the given problems and detect relationships between specific values and required computational effort in the solving process. Based on the results, it can be pointed out that the mean machine utilization rate and the mean machine slack constitute good indicators for the complicatedness of a BJSPT, even though more complex figures are still needed to cover the full range of effects. The thesis mainly contributes to the research in complex job shop scheduling by introducing and applying a permutation-based heuristic to the BJSPT. First, different classical encodings of a schedule are discussed with respect to redundancy and feasibility. A procedure to co