Search

A bi-criteria scheduling problem for parallel identical batch processing machines in semiconductor wafer fabrication facilities is studied. Only jobs belonging to the same family can be batched together. The performance measures are the total weighted tardiness and the electricity cost where a time-of-use (TOU) tariff is assumed. Unequal ready times of the jobs and non-identical job sizes are considered. A mixed integer linear program (MILP) is formulated. We analyze the special case where all jobs have the same size, all due dates are zero, and the jobs are available at time zero. Properties of Pareto-optimal schedules for this special case are stated. They lead to a more tractable MILP. We design three heuristics based on grouping genetic algorithms that are embedded into a non-dominated sorting genetic algorithm II framework. Three solution representations are studied that allow for choosing start times of the batches to take into account the energy consumption. We discuss a heuristic that improves a given near-to-optimal Pareto front. Computational experiments are conducted based on randomly generated problem instances. The $$ \varepsilon $$ ε -constraint method is used for both MILP formulations to determine the true Pareto front. For large-sized problem instances, we apply the genetic algorithms (GAs). Some of the GAs provide high-quality solutions.

In this paper, a production planning problem for mixed-model assembly lines in low-volume manufacturing as can be found in aircraft manufacturing is considered. This type of manufacturing is labor-intensive. Low-volume production of huge-sized jobs, i.e. airplanes, is typical. Balancing labor costs and inventory holding costs assuming a given job sequence is the purpose of this paper. Therefore, worker assignments to each station and start times and processing times for each job on each station are determined. Two different mathematical models are proposed. The first formulation is a time-indexed linear formulation that allows for a flexible allocation of workers to periods and stations while the second one has a non-linear objective function and allows only for a fixed assignment of workers to stations. It is proven that the second formulation leads to a linear program with continuous decision variables if the values of the decision variables that determine the number of workers assigned to a station are given, while the first formulation contains even in this situation binary decision variables. Heuristics that hybridize the mathematical formulations with variable neighborhood search techniques are proposed. Computational experiments on randomly generated problem instances and on real-world instances demonstrate the high performance of the heuristics.

In this paper, we discuss a flexible flow shop scheduling problem with batch processing machines at each stage and with jobs that have unequal ready times. Scheduling problems of this type can be found in semiconductor wafer fabrication facilities (wafer fabs). We are interested in minimizing the total weighted tardiness of the jobs. We present a mixed integer programming formulation. The batch scheduling problem is NP-hard. Therefore, an iterative stage-based decomposition approach is proposed that is hybridized with neighborhood search techniques. The decomposition scheme provides internal due dates and ready times for the jobs on the first and second stage, respectively. Each of the resulting parallel machine batch scheduling problems is solved by variable neighborhood search in each iteration. Based on the schedules of the subproblems, the internal due dates and ready times are updated. We present the results of designed computational experiments that also consider the number of machines assigned to each stage as a design factor. It turns out that the proposed hybrid approach outperforms an iterative decomposition scheme where a fairly simple heuristic based on time window decomposition and the apparent tardiness cost dispatching rule is used to solve the subproblems. Recommendations for the design of the two stages with respect to the number of parallel machines on each stage are given.

In this paper, we discuss scheduling problems motivated by a real-world production setting found in 300-mm semiconductor wafer fabrication facilities (wafer fabs). Front opening unified pods (FOUPs) transfer wafers in 300-mm wafer fabs. Several orders can be grouped in one FOUP. We study lot and single item processing environments. The total weighted tardiness (TWT) and the weighted number of tardy orders (WNTO) objectives are considered. Mixed integer programming (MIP) formulations are presented for the scheduling problems. We prove that the researched scheduling problems are NP-hard. Grouping genetic algorithms (GGAs) are proposed to form the content of the FOUPs. We compare the performance of the GGAs with another GA from the literature available for the problem with TWT measure based on randomly generated problem instances. It turns out that the GGA outperforms the heuristic from the literature for both environments. For the WTNO measure, we assess the performance of the GGA approach using MIP formulations for small-size problem instances and a GA-based heuristic for large-size problem instances. Again, the GGA performs well with respect to solution quality and amount of computing time.

Dienstkompositionen werden dazu verwendet, Geschaftsprozesse in einer Vielzahl von Anwendungsdomanen zu implementieren. Die Quality-of-Service (QoS)-basierte Auswahl von Diensten berucksichtigt mehrere, typischerweise konfliktare und moglicherweise unsichere QoS-Attribute. Ein multikriterieller Losungsansatz ist wunschenswert, um eine Menge alternativer Dienstselektionen zu ermitteln. Auserdem ist festzustellen, dass die Unsicherheit von QoS-Attributen in existierenden Ansatzen vernachlassigt wird. Daraus folgt, dass es erforderlich ist, Dienst-Rekonfigurationen zu betrachten, um eine Verletzung von QoS-Restriktionen zu vermeiden. Das in der Arbeit untersuchte Problem ist NP-schwer. Der Artikel stellt einen heuristischen multikriteriellen Dienstauswahlansatz vor, der dazu entworfen wurde, eine Pareto-Front alternativer Dienstselektionen mit vertretbarem Rechenaufwand zu ermitteln. Die erhaltenen Dienstselektionen sind robust bezuglich einer eingeschrankten Ausfuhrungsdauer, wenn unsichere Antwortzeiten berucksichtigt werden. Der vorgeschlagene Losungsansatz basiert auf einem Nondominated Sorting Genetic Algorithm (NSGA-II)-Ansatz, der problemspezifische Eigenschaften ausnutzt. Die Anwendbarkeit des vorgeschlagenen Losungsansatzes wird durch eine Simulationsstudie gezeigt.

Service compositions are used to implement business processes in a variety of application domains. A quality of service (QoS)-aware selection of the service to be composed involves multiple, usually conflicting and possibly uncertain QoS attributes. A multi-criteria solution approach is desired to generate a set of alternative service selections. In addition, the uncertainty of QoS-attributes is neglected in existing solution approaches. Hence, the need for service reconfigurations is imposed to avoid the violation of QoS restrictions. The researched problem is NP-hard. This article presents a heuristic multi-criteria service selection approach that is designed to determine a Pareto frontier of alternative service selections in a reasonable amount of time. Taking into account the uncertainty of response times, the obtained service selections are robust with respect to the constrained execution time. The proposed solution approach is based on the Non-dominated Sorting Genetic Algorithm (NSGA)-II extended by heuristics that exploit problem specific characteristics of the QoS-aware service selection. The applicability of the solution approach is demonstrated by a simulation study.

In dem Artikel skizzieren wir einige der Herausforderungen, die in zukunftigen Forschungsaktivitaten fur eine modellbasierte Entscheidungsunterstutzung in Produktions- und Dienstleistungsnetzwerken zu adressieren sind. Das beinhaltet die Betrachtung von Integrationsaspekten, insbesondere auch unter Berucksichtigung der Autonomie von Entscheidungstragern und Informationsasymmetrie, die Modellierung von Praferenzen der Entscheider, die effiziente Ermittlung robuster Losungen, d. h. Losungen, die unempfindlich bezuglich Anderungen in den Problemdaten sind, und eine Verkurzung der Zeit zur Modellerstellung und -nutzung. Der Problemlosungszyklus umfasst eine Problemanalyse, den Entwurf geeigneter Algorithmen sowie deren Leistungsbewertung. Wir sind an einer prototypischen Integration der vorgeschlagenen Methoden in Anwendungssysteme interessiert. Daran anschliesend konnen Feldtests mit den so erweiterten Anwendungssystemen durchgefuhrt werden. Die vorgeschlagene Forschungsagenda erfordert eine interdisziplinare Zusammenarbeit von Wirtschaftsinformatikern mit Kollegen aus der Betriebswirtschaftslehre, der Informatik und dem Operations Research. Auserdem werden exemplarisch einige Beispiele fur relevante Forschungsergebnisse vorgestellt.

In this paper, we consider a parallel machine scheduling problem to minimize the total completion time. Each job belongs to a certain family. All jobs of one family have identical processing times. Major setups occur between jobs of different families, and we include sequence dependencies. Batches of jobs belonging to the same family can be formed to avoid these setups. Furthermore, we assume serial batching and batch availability. Therefore, the processing time of a batch is the sum of the processing times of all jobs grouped into the corresponding batch. An iterative method is developed for solving this specific problem. This approach alternates between varying batch sizes using an efficient heuristic and sequencing batches based on variable neighborhood search (VNS). Computational results demonstrate that the iterative heuristic outperforms heuristics based on a fixed batch size and list scheduling.

In this paper, we address a parallel machine scheduling problem to minimize the total weighted completion time, where product families are involved. Major setups occur when processing jobs of different families, and sequence dependencies are also taken into account. Considering its high practical relevance, we focus on the special case where all jobs of the same family have identical processing times. In order to avoid redundant setups, batching jobs of the same family can be performed. We first develop a variable neighborhood search algorithm (VNS) to solve the interrelated subproblems in a simultaneous manner. To further reduce computing time, we also propose an iterative scheme which alternates between a specific heuristic to form batches and a VNS scheme to schedule entire batches. Computational experiments are conducted which confirm the benefits of batching. Test results also show that both simultaneous and iterative approach outperform heuristics based on a fixed batch size and list scheduling. Furthermore, the iterative procedure succeeds in balancing solution quality and computing time.

In this paper, a model-based planning approach within the framework of distributed hierarchical enterprise management is developed. Suitable algorithms are provided, especially for the case of manufacturing companies. Requirements for a decision support system based on this concept are derived. Software agents in the context of a Multi-Agent-System (MAS) seem to be appropriate to implement the proposed concept. After the identification of the necessary agents, the system architecture is described. Computational results for the suggested algorithm are discussed.

In this paper, we study a planning and scheduling problem for unrelated parallel machines. There are n jobs that have to be assigned and sequenced on m unrelated parallel machines. Each job has a weight that represents the priority of the corresponding customer order, a given due date, and a release date. An Automated Guided Vehicle is used to transport at maximum Load max jobs into a storage space in front of the machines in a given period of time. We consider t max consecutive periods. We are interested in minimizing the total weighted tardiness of the jobs across the periods. This measure is important when we are interested in a good on-time delivery performance. We present an appropriate mixed integer program. To solve this NP-hard problem, we develop a heuristic methodology based on decomposition and variable neighborhood search (VNS). The proposed approaches are assessed using randomly generated problem instances. We compare them with a simple heuristic based on decomposition and list scheduling using the Apparent Tardiness Cost dispatching rule. The results demonstrate that the heuristic approach based on VNS performs comparably to the mixed integer program while having reasonable solution times and outperforms the simple heuristic and a genetic algorithm (GA) from previous research.

Der Beitrag beschreibt einen Bezugsrahmen (Framework) fur eine verteilte hierarchische Steuerung komplexer Produktionsprozesse und dessen softwaretechnische Realisierung in Form von Multi-Agenten-Systemen. Es werden: drei Steuerungsebenen, die eine verteilte hierarchische Steuerung ermoglichen, beschrieben und Steuerungsverfahren vorgeschlagen, die zur hierarchischen Struktur der Steuerungsanwendung korrespondieren Design-und Implementierungsentscheidungen fur eine prototypische Steuerungsanwendung in Form eines Multi-Agenten-Systems dargestellt Ergebnisse einer simulationsbasierten Leistungsbewertung des verteilten Steuerungsansatzes fur die Domane Halbleiterfertigung, die eine Eignung des Frameworks zur Steuerung komplexer Produktionssysteme belegen, diskutiert.

This paper considers a scheduling problem for a single burn-in oven in the semiconductor manufacturing industry where the oven is a batch processing machine with restricted capacity. The batch processing time is set by the longest processing time among those of all the jobs contained in the batch. All jobs are assumed to have the same due date. The objective is to minimize the sum of the absolute deviations of completion times from the due date (earliness–tardiness) of all jobs under the constraint that the maximum tardiness should be less than or equal to the maximum allowable time value. We suggest several two-phase heuristic algorithms for this problem. In the first phase, some heuristic algorithms are developed without maximum allowable tardiness constraint. If the schedule from the first phase violates the maximum tardiness constraint, then the schedule is changed to satisfy maximum allowable tardiness constraint in the second phase. The suggested heuristics are based on genetic algorithms and dominance properties of optimal schedules. We present the results of computational experiments that clearly show the solution quality obtained by the suggested heuristics.

In this paper, we present a framework for the implementation of multi-agent-systems for production control of complex manufacturing systems. We present the results of a requirement analysis for production control systems for complex manufacturing systems; then we describe the framework design criteria. Our framework supports the inclusion of distributed hierarchical decision-making schemes into the production control. Furthermore, in order to increase the coordination abilities of multi-agent-systems, we follow the decision-making and staff agent architecture suggested in the PROSA reference architecture. We indicate the usage of the framework for designing and implementing an agent-based production control system for semiconductor manufacturing processes in a case study.

The paper describes a framework for parallel machine scheduling in complex manufacturing systems. Complex manufacturing systems are characterized by groups of parallel machines, machine dedications, sequence dependent setup times, batch processes, prescribed due dates of the jobs, and a diverse and over time changing product mix. In the present paper, a four-phase algorithm is suggested that covers a broad range of process conditions. The frameworks contains a first phase that deals with the formation of scheduling entities. The second phase is used to assign the scheduling entities to the parallel machines. The sequence of the scheduling entities is determined in the third phase on each single machine. The schedules are improved by the final, optional fourth phase. The paper describes software development issues, the integration of the framework into other information systems on the shopfloor, and the performance assessment of a case study.

Im Rahmen eines Forschungsvorhabens des Umweltbundesamts, Berlin, wurde die WTZ Roslau gGmbH beauftragt, reprasentative Daten zum Schadstoffemissionsverhalten von Schienendieselmotoren zu ermitteln. Kooperationspartner waren das IFEU-Institut, Heidelberg, und die Deutsche Bahn AG. Den Schwerpunkt der Untersuchungen bildeten Motoren mit einer Nennleistung uber 560 kW. Neben einer Standortbestimmung dieser Motorenkategorie war auch die Schaffung der Voraussetzungen zur Emissionsmodellierung fur den dieselbetriebenen Schienenverkehr in Deutschland ein wichtiges Ziel der Arbeiten.

As part of a research project initiated by the German Umweltbundesamt (Federal Environment Office) Berlin, WTZ Rosslau gGmbH was commissioned to gather representative data on the pollution behaviour of railway diesel engines. Other partners in the project were the IFEU Institute Heidelberg and Deutsche Bahn AG. Studies focused primarily on engines rated at over 560 kW. Besides taking overall stock of this category of engine, work was also targeted towards creating the preconditions for modelling the emissions produced by diesel-powered rail traffic in Germany.