A priority rule for minimizing weighted flow time in a class of parallel machine scheduling problems

The problem of scheduling n jobs with known process times on m identical parallel machines with an objective of minimizing weighted flow time is NP-hard. However, when job weights are identical, it is well known that the problem is easily solved using the shortest processing time rule. In this paper, we show that a generalization of the shortest processing time rule minimizes weighted flow time in a class of problems where job weights are not identical.     

Minimizing the weighted number of tardy jobs on a single machine with release dates

In this paper, we describe an exact algorithm to minimize the weighted number of tardy jobs on a single machine with release dates. The algorithm uses branch-and-bound; a surrogate relaxation resulting in a multiple-choice knapsack provides the bounds. Extensive computational experiments indicate the proposed exact algorithm solves either weighted or unweighted problems. It solves the hardest problems to date. Indeed, it solves all previously unsolved instances. Its run time is the shortest to date.     

An approximate algorithm for a high-multiplicity parallel machine scheduling problem

We consider a high-multiplicity parallel machine scheduling problem where the objective is to minimize the weighted sum of completion times. We suggest an approximate algorithm and we prove that it is asymptotically exact. The algorithm exploits a convex quadratic relaxation of the problem to fix a partial schedule, consisting of most jobs, and then assigns the residual jobs following a simple and general rule. The quality of the obtained solution is evidenced by some numerical tests.     

Parallel-machine scheduling with non-simultaneous machine available time

We consider a problem of scheduling n independent jobs on m parallel identical machines. The jobs are available at time zero, but the machines may not be available simultaneously at time zero. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time and total absolute differences in completion times; minimizing a cost function containing total waiting time and total absolute differences in waiting times. In this paper, we present polynomial time algorithm to solve this problem.     

Single machine scheduling under market uncertainty

This paper considers single machine scheduling problems where job processing times are known and deterministic but where the reward received upon completion of a job changes stochastically over time according to Brownian motion. The objectives of maximizing expected net-present-value (NPV), minimizing the variance of NPV and maximizing the probability of achieving a minimum benchmark NPV are considered. For non-preemptive static list policies complexity results and branch and bound procedures are presented. The branch and bound procedures are shown to be effective for problem instances with 20–25 jobs. For the problem of maximizing NPV with non-preemptive dynamic policies the optimal static schedule is shown through empirical testing to be as good as a greedy heuristic and to be near optimal when the variance is not large.     

Scheduling on parallel identical machines to minimize total tardiness

This paper focuses on the problem of scheduling n independent jobs on m identical parallel machines for the objective of minimizing total tardiness of the jobs. We develop dominance properties and lower bounds, and develop a branch and bound algorithm using these properties and lower bounds as well as upper bounds obtained from a heuristic algorithm. Computational experiments are performed on randomly generated test problems and results show that the algorithm solves problems with moderate sizes in a reasonable amount of computation time.     

Note on Shim and Kim’s lower bounds for scheduling on identical parallel machines to minimize total tardiness

This note introduces a new lower bound for the problem of scheduling on parallel identical machines to minimize total tardiness that is based on the concepts used in the two lower bounds developed by Shim and Kim [Shim, S.O., Kim, Y.D., 2007. Scheduling on parallel identical machines to minimize total tardiness. European Journal of Operational Research 177, 135–146]. The note shows that the new lower bound dominates the three lower bounds used in Shim and Kim’s branch-and-bound algorithm and can be used in place of these lower bounds to lower the enumeration required.     

Parallel machine scheduling with machine availability and eligibility constraints

In this paper we consider the problem of scheduling n independent jobs on m identical machines incorporating machine availability and eligibility constraints while minimizing the makespan. Each machine is not continuously available at all times and each job can only be processed on specified machines. A network flow approach is used to formulate this scheduling problem into a series of maximum flow problems. We propose a polynomial time binary search algorithm to either verify the infeasibility of the problem or solve it optimally if a feasible schedule exists.     

An exact approach for single machine subproblems in shifting bottleneck procedures for job shops with total weighted tardiness objective

In this paper, we propose an exact solution method for single machine scheduling problems typically arising from bottleneck-based decomposition of weighted tardiness job shops. The encountered subproblems are characterized by delayed precedence constraints, multiple local due dates per operation and an objective function that is given by a weighted sum of maximum tardiness values. The key concept for solving these subproblems to optimality is a dominance rule whose underlying concepts have been newly developed to cope with the given structural properties. Furthermore, a simple lower bound and a dedicated constraint programming technique are presented. The efficiency of the proposed method is demonstrated by means of single machine problems collected during a run of a shifting bottleneck procedure for job shops in different size and due date tightness configurations.     

Minimizing total tardiness on a two-machine re-entrant flowshop

We present a branch and bound algorithm for a two-machine re-entrant flowshop scheduling problem with the objective of minimizing total tardiness. In the re-entrant flowshop considered here, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. By regarding a job as a pair of sub-jobs, each of which represents a pass through the two machines, we develop dominance properties, a lower bound and heuristic algorithms for the problem, and use these to develop a branch and bound algorithm. For evaluation of the performance of the algorithms, computational experiments are performed on randomly generated test problems and results are reported. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 20 sub-jobs in a reasonable amount of CPU time, and the average percentage gap of the heuristic solutions is about 13%.     

Parallel machine scheduling with additional resources: Notation,classification, models and solution methods

Majority of parallel machine scheduling studies consider machine as the only resource. However, in most real-life manufacturing environments, jobs may require additional resources, such as automated guided vehicles, machine operators, tools, pallets, dies, and industrial robots, for their handling and processing. This paper presents a review and discussion of studies on the parallel machine scheduling problems with additional resources. Papers are surveyed in five main categories: machine environment, additional resource, objective functions, complexity results and solution methods, and other important issues. The strengths and weaknesses of the literature together with open areas for future studies are also emphasized. Finally, extensions of integer programming models for two main classes of related problems are given and conclusions are drawn based on computational studies.     

Complexities and algorithms for synchronized scheduling of parallel machine assembly and air transportation in consumer electronics supply chain

In this paper, we study the problem of synchronized scheduling of assembly and air transportation to achieve accurate delivery with minimized cost in consumer electronics supply chain. This problem was motivated by a major PC manufacturer in consumer electronics industry. The overall problem is decomposed into two sub-problems, which consist of an air transportation allocation problem and an assembly scheduling problem. The air transportation allocation problem is formulated as an integer linear programming problem with the objective of minimizing transportation cost and delivery earliness tardiness penalties. The assembly scheduling problem seeks to determine a schedule ensuring that the orders are completed on time and catch the flights such that the waiting penalties between assembly and transportation is minimized. The problem is formulated as a parallel machine scheduling problem with earliness penalties. The computational complexities of the two sub-problems are investigated. The air transportation allocation problem with split delivery is shown to be solvable. The parallel machine assembly scheduling problem is shown to be NP-complete. Simulated annealing based heuristic algorithms are presented to solve the parallel machine problem.     

Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs

This paper studies the parallel machines bi-criteria scheduling problem (PMBSP) in a deteriorating system. Sequencing and scheduling problems (SSP) have seldom considered the two phenomena concurrently. This paper discusses the parallel machines scheduling problem with the effects of machine and job deterioration. By the machine deterioration effect, we mean that each machine deteriorates at a different rate. This deterioration is considered in terms of cost which depends on the production rate, the machine’s operating characteristics and the kind of work done by each machine. Moreover, job processing times are increasing functions of their starting times and follow a simple linear deterioration. The objective functions are minimizing total tardiness and machine deteriorating cost. The problem of total tardiness on identical parallel machines is NP-hard, thus the problem with machine deteriorating cost as an additional term is also NP-hard. We propose the LP-metric method to show the importance of our proposed multi-objective problem. A metaheuristic algorithm is developed to locate optimal or near optimal solutions based on a Tabu search mechanism. Numerical examples are presented to show the efficiency of this model.     

An exact algorithm to minimize mean squared deviation of job completion times about a common due date

We consider a deterministic n-job, single machine scheduling problem with the objective of minimizing the Mean Squared Deviation (MSD) of job completion times about a common due date (d). The MSD measure is non-regular and its value can decrease when one or more completion times increases. MSD problem is connected with the Completion Time Variance (CTV) problem and has been proved to be NP-hard. This problem finds application in situations where uniformity of service is important. We present an exact algorithm of pseudo-polynomial complexity, using ideas from branch and bound and dynamic programming. We propose a dominance rule and also develop a lower bound on MSD. The dominance rule and lower bound are effectively combined and used in the development of the proposed algorithm. The search space is explored using the breadth first branching strategy. The asymptotic space complexity of the algorithm is O(nd). Irrespective of the version of the problem – tightly constrained, constrained or unconstrained – the proposed algorithm provides optimal solutions for problem instances up to 1000 jobs size under different due date settings.     

Mixed-integer linear programming for resource leveling problems

We consider project scheduling problems subject to general temporal constraints, where the utilization of a set of renewable resources has to be smoothed over a prescribed planning horizon. In particular, we consider the classical resource leveling problem, where the variation in resource utilization during project execution is to be minimized, and the so-called “overload problem”, where costs are incurred if a given resource-utilization threshold is exceeded. For both problems, we present new mixed-integer linear model formulations and domain-reducing preprocessing techniques. In order to strengthen the models, lower and upper bounds for resource requirements at particular points in time, as well as effective cutting planes, are outlined. We use CPLEX 12.1 to solve medium-scale instances, as well as instances of the well-known test set devised by Kolisch et al. (1999). Instances with up to 50 activities and tight project deadlines are solved to optimality for the first time.     

An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines

We propose an off-line delayed-start LPT algorithm that sequences the first (longest) 5 jobs optimally and the remaining jobs according to the LPT principle on two identical parallel machines. We show that this algorithm has a sharper tight worst-case ratio bound than the traditional LPT algorithm for the sum of squares of machine completion times minimization problem.     

On a resource-constrained scheduling problem with application to distributed systems reconfiguration

This paper is devoted to the study of a resource-constrained scheduling problem, the Process Move Programming problem, which arises in relation to the operability of certain high availability real-time distributed systems. Informally, this problem consists, starting from an arbitrary initial distribution of processes on the processors of a distributed system, in finding the least disruptive sequence of operations (non-impacting process migrations or temporary process interruptions) at the end of which the system ends up in another predefined arbitrary state. The main constraint is that the capacity of the processors must not be exceeded during the reconfiguration. After a brief survey of the literature, we prove the NP-hardness of the problem and exhibit a few polynomial special cases. We then present a branch-and-bound algorithm for the general case along with computational results demonstrating its practical relevance. The paper is concluded by a discussion on further research.     

Minimizing total tardiness in parallel machine scheduling with setup times: An adaptive memory-based GRASP approach

This paper deals with the problem of scheduling jobs in uniform parallel machines with sequence-dependent setup times in order to minimize the total tardiness relative to job due dates. We propose GRASP versions that incorporate adaptive memory principles for solving this problem. Long-term memory is used in the construction of an initial solution and in a post-optimization procedure which connects high quality local optima by means of path relinking. Computational tests are carried out on a set of benchmark instances and the proposed GRASP versions are compared with heuristic methods from the literature.     

Minimizing the sum of job completion times on capacitated two-parallel machines

This paper considers a scheduling problem with two identical parallel machines. One has unlimited capacity; the other can only run for a fixed time. A given set of jobs must be scheduled on the two machines with the goal of minimizing the sum of their completion times. The paper proposes an optimal branch and bound algorithm which employs three powerful elements, including an algorithm for computing the upper bound, a lower bound algorithm, and a fathoming condition. The branch and bound algorithm was tested on problems of various sizes and parameters. The results show that the algorithm is quite efficient to solve all the test problems. In particular, the total computation time for the hardest problem is less than 0.1 second for a set of 100 problem instances. An important finding of the tests is that the upper bound algorithm can actually find optimal solutions to a quite large number of problems.     

Combined vehicle routing and scheduling with temporal precedence and synchronization constraints

We present a mathematical programming model for the combined vehicle routing and scheduling problem with time windows and additional temporal constraints. The temporal constraints allow for imposing pairwise synchronization and pairwise temporal precedence between customer visits, independently of the vehicles. We describe some real world problems where in the literature the temporal constraints are usually remarkably simplified in the solution process, even though these constraints may significantly improve the solution quality and/or usefulness. We also propose an optimization based heuristic to solve real size instances. The results of numerical experiments substantiate the importance of the temporal constraints in the solution approach. We also make a computational study by comparing a direct use of a commercial solver against the proposed heuristic, where the latter approach can find high quality solutions within specific time limits.