Search

Flow shops are widely studied machine environments in which all jobs must visit all machines in the same order. While conventional flow shops assume that each job traverses the shop only once, many industrial environments require jobs to loop through the shop multiple times before completion. This means that after traversing the shop and completing its processing on the last machine, a job must return to the first machine and traverse the shop again until it has completed all its required loops. Such a setting, referred to as a flow shop with reentry, has numerous applications in industry, e.g., semiconductor manufacturing. The planning problem is to schedule all loops of all jobs while minimizing the total weighted completion time. In this paper, we consider reentrant flow shops with unit processing times. We show that this problem is strongly NP-hard if the number of machines is part of the input. We propose the Least Remaining Loops First (LRL) priority rule and show that it minimizes the total unweighted completion time. Then, we analyze the Weighted Least Remaining Loops First (WLRL) priority rule and show that it has a worst-case performance ratio of $(1+\sqrt{2})/2$ (about 1.2). Additionally, we present a fully polynomial time approximation scheme (FPTAS) and a pseudo-polynomial time algorithm if the number of machines in the flow shop is fixed.

This paper resolves a long-standing open question in bicriteria scheduling regarding the complexity of a single machine scheduling problem which combines the number of tardy jobs and the maximal tardiness criteria. We use the lexicographic approach with the maximal tardiness being the primary criterion. Accordingly, the objective is to find, among all solutions minimizing the maximal tardiness, the one which has the minimum number of tardy jobs. The complexity of this problem has been open for over thirty years, and has been known since then to be one of the most challenging open questions in multicriteria scheduling. We resolve this question by proving that the problem is strongly NP-hard. We also prove that the problem is at least weakly NP-hard when we switch roles between the two criteria (i.e., when the number of tardy jobs is the primary criterion). Finally, we provide hardness results for two other approaches (constraint and a priori approaches) to deal with these two criteria.

Recent research found that fairness plays a key role in customer satisfaction. Therefore, many manufacturing and services industries have become aware of the need to treat customers fairly. Still, there is a huge lack of models that enable industries to make operational decisions fairly, such as a fair scheduling of the customers' jobs. Our main aim in this research is to provide a unified framework to enable schedulers making fair decisions in repetitive scheduling environments. For doing so, we consider a set of repetitive scheduling problems involving a set of $n$ clients. In each out of $q$ consecutive operational periods (e.g. days), each one of the customers submits a job for processing by an operational system. The scheduler's aim is to provide a schedule for each of the $q$ periods such that the quality of service (QoS) received by each of the clients will meet a certain predefined threshold. The QoS of a client may take several different forms, e.g., the number of days that the customer receives its job later than a given due-date, the number of times the customer receive his preferred time slot for service, or the sum of waiting times for service. We analyze the single machine variant of the problem for several different definitions of QoS, and classify the complexity of the corresponding problems using the theories of classical and parameterized complexity. We also study the price of fairness, i.e., the loss in the system's efficiency that results from the need to provide fair solutions.