Lawler’s minmax cost problem under uncertainty

The well-known \(O(n^2)\) minmax cost algorithm of Lawler (Manag Sci 19(5):544–546, 1973) was developed to minimize the maximum cost of jobs processed by a single machine under precedence constraints. We first develop a fast updating algorithm to obtain optimal solutions for two neighboring instances. This method will be used throughout this article. Then we consider job cost functions that depend on the completion time and on one or more additional numerical parameters. The parameters are uncertain and take values from given intervals. Under the uncertainty, we apply the minmax regret criterion for choosing a solution. We generalize results by Brauner et al. (J Sched, 2015) for decomposable cost functions with deterministic processing times and a single uncertain parameter to general cost functions. We describe different conditions, under which minmax regret solutions can be obtained with the time complexity \(O(n^3)\) or \(O(n^2)\). Then the updating algorithm is applied to the lateness model by Kasperski (Oper Res Lett 33:431–436, 2005) where both the processing time and the due date of each job are uncertain. The original \(O(n^4)\) running time is improved to the time complexity \(O(n^3)\). Finally, we extend the cost functions with a single uncertain parameter to those with a vector of additional uncertain parameters, improve one of the complexity results by Volgenant and Duin (Comput Oper Res 37:909–915, 2010) and solve some new problems.     

Scheduling dedicated jobs with variative processing times

We consider the following optimization problem. There is a set of \(n\) dedicated jobs that are to be processed on \(m\) parallel machines. The job set is partitioned into subsets and jobs of each subset have a common due date. Processing times of jobs are interconnected and they are the subject of the decision making. The goal is to choose a processing time for each job in a feasible way and to construct a schedule that minimizes the maximum lateness. We show that the problem is NP-hard even if \(m=1\) and that it is NP-hard in the strong sense if \(m\) is a variable. We prove that there is no approximate polynomial algorithm with guaranteed approximation ratio less than 2. We propose an integer linear formulation for the problem and perform experiments. The experiments show that the solutions obtained with CPLEX within the limit of 5 min are on average about 5 % from the optimum value for instances with up to 150 jobs, 16 subsets and 11 machines. Most instances were solved to optimality and the average CPLEX running time was 32 s for these instances.     

Flow Shop Scheduling Problems Under Machine–Dependent Precedence Constraints

The paper considers the flow shop scheduling problems to minimize the makespan, provided that an individual precedence relation is specified on each machine. A fairly complete complexity classification of problems with two and three machines is obtained.