A hybrid two-stage transportation and batch scheduling problem

We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances.     

Range of lower bounds

Each of n jobs is to be processed without interruption on a single machine. Each job becomes available for processing at time zero. The objective is to find a processing order of the jobs which minimizes the sum of weighted completion times added with maximum weighted tardiness. In this paper we give a general case of the theorem that given in [6]. This theorem shows a relation between the number of efficient solutions, lower bound LB and optimal solution. It restricts the range of the lower bound, which is the main factor to find the optimal solution. Also, the theorem opens algebraic operations and concepts to find new lower bounds.     

Single-machine scheduling of proportionally deteriorating jobs by two agents

We consider a problem of scheduling a set of independent jobs by two agents on a single machine. Every agent has its own subset of jobs to be scheduled and uses its own optimality criterion. The processing time of each job proportionally deteriorates with respect to the starting time of the job. The problem is to find a schedule that minimizes the total tardiness of the first agent, provided that no tardy job is allowed for the second agent. We prove basic properties of the problem and give a lower bound on the optimal value of the total tardiness criterion. On the basis of these results, we propose a branch-and-bound algorithm and an evolutionary algorithm for the problem. Computational experiments show that the exact algorithm solves instances up to 50 jobs in a reasonably short time and that solutions obtained by the metaheuristic are close to optimal ones.     

A heuristic for scheduling in a two-stage hybrid flowshop with renewable resources shared among the stages

In this paper we propose a heuristic for solving the problem of resource constrained preemptive scheduling in the two-stage flowshop with one machine at the first stage and parallel unrelated machines at the second stage, where renewable resources are shared among the stages, so some quantities of the same resource can be used at different stages at the same time. Availability of every resource at any moment is limited and resource requirements of jobs are arbitrary. The objective is minimization of makespan. The problem is NP-hard. The heuristic first sequences jobs on the machine at stage 1 and then solves the preemptive scheduling problem at stage 2. Priority rules which depend on processing times and resource requirements of jobs are proposed for sequencing jobs at stage 1. A column generation algorithm which involves linear programming, a tabu search algorithm and a greedy procedure is proposed to minimize the makespan at stage 2. A lower bound on the optimal makespan in which sharing of the resources between the stages is taken into account is also derived. The performance of the heuristic evaluated experimentally by comparing the solutions to the lower bound is satisfactory.     

Single-machine scheduling with deteriorating jobs and learning effects to minimize the makespan

This paper studies the single-machine scheduling problem with deteriorating jobs and learning considerations. The objective is to minimize the makespan. We first show that the schedule produced by the largest growth rate rule is unbounded for our model, although it is an optimal solution for the scheduling problem with deteriorating jobs and no learning. We then consider three special cases of the problem, each corresponding to a specific practical scheduling scenario. Based on the derived optimal properties, we develop an optimal algorithm for each of these cases. Finally, we consider a relaxed model of the second special case, and present a heuristic and analyze its worst-case performance bound.     

Minimizing the number of machines with limited workload capacity for scheduling jobs with interval constraints

In this paper, we consider a parallel machine scheduling problem in which machines have a limited workload capacity and jobs have deadlines and release dates. The problem is motivated by the operation of energy storage management systems for microgrids under emergency conditions and generalizes some problems that have already been studied in the literature for their theoretical value. In this work, we propose heuristic and exact algorithms to solve the problem. The heuristics are adaptations of classical bin packing heuristics in which additional conditions on the feasibility of a solution are imposed, whereas the exact method is a branch-and-price approach. The results show that the branch-and-price approach is able to optimally solve random instances with up to 250 jobs within a time limit of one hour, while the heuristic procedures provide near optimal solution within reduced running times. Finally, we also provide additional complexity results for a special case of the problem.     

Minmax earliness–tardiness costs with unit processing time jobs

The problem addressed in this paper is defined by M parallel identical machines, N jobs with identical (unit) processing time, job-dependent weights, and a common due-date for all jobs. The objective is of a minmax type, i.e. we are interested in minimizing the cost of the worst scheduled job. In the case of a non-restrictive (i.e., sufficiently large) common due-date, the problem is shown to have a solution that is polynomial in the number of jobs. The solution in the case of a restrictive due-date remains polynomial in the number of jobs, but is exponential in the number of machines. We introduce a lower bound on the optimal cost and an efficient heuristic. We show that the worst case relative error of the heuristic is bounded by 2 and that this bound is tight. We also prove that the heuristic is asymptotically optimal under very general assumptions. Finally, we provide an extensive numerical study demonstrating that in most cases the heuristic performs extremely well.     

Scheduling coupled-operation jobs with exact time-lags

Scheduling coupled-operation jobs with exact time-lags on a single machine has a wide range of applications. In that problem, each job consists of two operations with given processing times, which should be scheduled on a single machine observing a given time-lag. The general case of the problem with arbitrary processing times of operations and arbitrary time lags is known to be NP-hard in the strong sense and the problem remains NP-hard for many special cases. In order to develop a local search algorithm for the problem, we first explore two possible approaches for representing feasible solutions and their neighborhoods based on maintaining a permutation of first operations of the jobs or maintaining a full permutation of all operations. The first representation appears to be unpromising since, as we prove, the problem of finding an optimal sequence of second operations for a fixed sequence of first operations is NP-hard in the strong sense even in the case of unit processing times. We elaborate the second approach by developing a tabu search heuristic based on efficient job re-insertion. Empirical evaluation demonstrates superiority of the developed algorithm in comparison with the earlier published algorithms.     

Minimizing makespan in parallel flowshops

In this study, a new class of proportional parallel flow shop problems with the objective of minimizing the makespan has been addressed. A special case for this problem in which jobs are processed on only one machine as opposed to two or more machines in a flow shop, is the well-known multiple processor problem which is NP-complete. The parallel processor problem is a restricted version of the problems addressed in this paper and hence are NP-complete. We develop and test heuristic and simulation approaches to solve large scale problems, while using exact procedures for smaller problems. The performance of the heuristics relative to the LP lower bound as well as a comparison with the truncated integer programming solution are reported. The performance of the heuristics and the simulation results were encouraging.     

A branch and bound based heuristic for makespan minimization of washing operations in hospital sterilization services

In this paper, we address the problem of parallel batching of jobs on identical machines to minimize makespan. The problem is motivated from the washing step of hospital sterilization services where jobs have different sizes, different release dates and equal processing times. Machines can process more than one job at the same time as long as the total size of jobs in a batch does not exceed the machine capacity. We present a branch and bound based heuristic method and compare it to a linear model and two other heuristics from the literature. Computational experiments show that our method can find high quality solutions within short computation time.     

The flow shop problem with no-idle constraints: A review and approximation

The makespan minimization problem in flow shops with no-idle constraints on machines is considered. The latter means that each machine, once started, must process all its operations without intermediate idle time until all those operations are completed. The problem is known to be strongly NP-hard already for three machines. While being based on a geometrical approach, we propose several polynomial time heuristics (for the general case and for special cases of 3 and 4 machines) which provide asymptotically optimal solutions for the increasing number of jobs. A comprehensive review of relevant results is also presented.     

Reducing work-in-process movement for multiple products in one-dimensional layout problems

This research describes a method to assign M machines, which are served by a material handling transporter, to M equidistant locations along a track, so that the distance traveled by a given set of jobs is minimized. Traditionally, this problem (commonly known as a machine location problem) has been modeled as a quadratic assignment problem (QAP), which is NP-hard, thus motivating the need for efficient procedures to solve instances with several machines. In this paper we develop a branching heuristic to obtain sub-optimum solutions to the problem; a lower bound on the optimum solution has also been presented. Results obtained from the heuristics are compared with results obtained from other heuristics with similar objectives. It is observed that the results are promising, and justify the usage of developed methods.     

Optimal allocation and processing time decisions on non-identical parallel CNC machines: ϵ-constraint approach

When the processing times of jobs are controllable, selected processing times affect both the manufacturing cost and the scheduling performance. A well known example for such a case that this paper specifically deals with is the turning operation on a CNC machine. Manufacturing cost of a turning operation is a nonlinear convex function of its processing time. In this paper, we deal with making optimal machine-job assignments and processing time decisions so as to minimize total manufacturing cost while the makespan being upper bounded by a known value, denoted as ?-constraint approach for a bicriteria problem. We then give optimality properties for the resulting single criterion problem. We provide alternative methods to compute cost lower bounds for partial schedules, which are used in developing an exact (branch and bound) algorithm. For the cases where the exact algorithm is not efficient in terms of computation time, we present a recovering beam search algorithm equipped with an improvement search procedure. In order to find improving search directions, the improvement search algorithm uses the proposed cost bounding properties. Computational results show that our lower bounding methods in branch and bound algorithm achieve a significant reduction in the search tree size that we need to traverse. Also, our recovering beam search and improvement search heuristics achieve solutions within 1% of the optimum on the average while they spent much less computational effort than the exact algorithm.     

A graph-theoretic approach to interval scheduling on dedicated unrelated parallel machines

We study the problem of scheduling n non-preemptive jobs on m unrelated parallel machines. Each machine can process a specified subset of the jobs. If a job is assigned to a machine, then it occupies a specified time interval on the machine. Each assignment of a job to a machine yields a value. The objective is to find a subset of the jobs and their feasible assignments to the machines such that the total value is maximized. The problem is NP-hard in the strong sense. We reduce the problem to finding a maximum weight clique in a graph and survey available solution methods. Furthermore, based on the peculiar properties of graphs, we propose an exact solution algorithm and five heuristics. We conduct computer experiments to assess the performance of our and other existing heuristics. The computational results show that our heuristics outperform the existing heuristics.     

Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times

In this paper, we study the identical parallel machine scheduling problem with a planned maintenance period on each machine to minimize the sum of completion times. This paper is a first approach for this problem. We propose three exact methods to solve the problem at hand: mixed integer linear programming methods, a dynamic programming based method and a branch-and-bound method. Several constructive heuristics are proposed. A lower bound, dominance properties and two branching schemes for the branch-and-bound method are presented. Experimental results show that the methods can give satisfactory solutions.     

Single machine earliness and tardiness scheduling

We examine the problem of scheduling a given set of jobs on a single machine to minimize total early and tardy costs without considering machine idle time. We decompose the problem into two subproblems with a simpler structure. Then the lower bound of the problem is the sum of the lower bounds of two subproblems. A lower bound of each subproblem is obtained by Lagrangian relaxation. Rather than using the well-known subgradient optimization approach, we develop two efficient multiplier adjustment procedures with complexity O(nlog n) to solve two Lagrangian dual subproblems. A branch-and-bound algorithm based on the two efficient procedures is presented, and is used to solve problems with up to 50 jobs, hence doubling the size of problems that can be solved by existing branch-and-bound algorithms. We also propose a heuristic procedure based on the neighborhood search approach. The computational results for problems with up to 3 000 jobs show that the heuristic procedure performs much better than known heuristics for this problem in terms of both solution efficiency and quality. In addition, the results establish the effectiveness of the heuristic procedure in solving realistic problems to optimality or near optimality.     

Machine scheduling with an availability constraint

Most literature in scheduling assumes that machines are available simultaneously at all times. However, this availability may not be true in real industry settings. In this paper, we assume that the machine may not always be available. This happens often in the industry due to a machine breakdown (stochastic) or preventive maintenance (deterministic) during the scheduling period. We study the scheduling problem under this general situation and for the deterministic case.We discuss various performance measures and various machine environments. In each case, we either provide a polynomial optimal algorithm to solve the problem, or prove that the problem is NP-hard. In the latter case, we develop pseudo-polynomial dynamic programming models to solve the problem optimally and/or provide heuristics with an error bound analysis.This research was supported in part by NSF grant DDM 9201627     

SINGLE MACHINE SCHEDULING WITH CONTROLLABLE PROCESSING TIMES AND COMPRESSION COSTS （Part Ⅱ Heuristics for the General Case）

A single machine scheduling problem with controllable processing times and compression costs is considered. The objective is to find an optimal sequence to minimize the cost ofcompletion times and the cost of compression. The complexity of this problem is still unknown.In Part Ⅱ of this paper,the authors have considered a special case where the compression timesand the compression costs are equal among all jobs. Such a problem appears polynomiafiy solvable by developing an O(n^2) algorithm. In this part(Part Ⅱ ),a general case where the controllable processing times and the compression costs are not equal is discussed. Authors proposehere two heuristics with the first based on some previous work and the second based on the algorithm developed in Part Ⅱ . Computational results are presented to show the efficiency and therobustness of these heuristics.     

A fast heuristic method for minimizing traffic congestion on reconfigurable ring topologies

We describe the development of fast heuristics and methodologies for congestion minimization problems in directional wireless networks, and we compare their performance with optimal solutions. The focus is on the network layer topology control problem (NLTCP) defined by selecting an optimal ring topology as well as the flows on it. Solutions to NLTCP need to be computed in near realtime due to changing weather and other transient conditions and which generally preclude traditional optimization strategies. Using a mixed-integer linear programming formulation, we present both new constraints for this problem and fast heuristics to solve it. The new constraints are used to increase the lower bound from the linear programming relaxation and hence speed up the solution of the optimization problem by branch and bound. The upper and lower bounds for the optimal objective function to the mixed integer problem then serve to evaluate new node-swapping heuristics which we also present. Through a series of tests on different sized networks with different traffic demands, we show that our new heuristics achieve within about 0.5% of the optimal value within seconds.     

Production scheduling with supply and delivery considerations to minimize the makespan

In this paper we study a scheduling model that simultaneously considers production scheduling, material supply, and product delivery. One vehicle with limited loading capacity transports unprocessed jobs from the supplier’s warehouse to the factory in a fixed travelling time. Another capacitated vehicle travels between the factory and the customer to deliver finished jobs to the customer. The objective is to minimize the arrival time of the last delivered job to the customer. We show that the problem is NP-hard in the strong sense, and propose an O(n) time heuristic with a tight performance bound of 2. We identify some polynomially solvable cases of the problem, and develop heuristics with better performance bounds for some special cases of the problem. Computational results show that all the heuristics are effective in producing optimal or near-optimal solutions quickly.