A Branch-and-Bound Approach for a Two-machine Flowshop Scheduling Problem

In this paper, we present a branch-and-bound approach for solving a two-machine flow shop scheduling problem, in which the objective is to minimize a weighted combination of job flowtime and schedule makespan. Experimental results show that the algorithm works very well for certain special cases and moderately well for others. In fact, it is able to produce optimal schedules for 500-job problems in which the second machine dominates the first machine. It is also shown that the algorithm developed to provide an upper bound for the branch-and-bound is optimal when processing times for jobs are the same on both machines. The primary reason for developing the branch-and-bound approach is that its results can be used to guide other heuristic techniques, such as simulated annealing, tabu search and genetic algorithms, in their search for optimal solutions for larger problems.     

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 combined approach for two-agent scheduling with sum-of-processing-times-based learning effect

This paper considers a scheduling model involving two agents, job release times, and the sum-of-processing-times-based learning effect. The sum-of-processing-times-based learning effect means that the actual processing time of a job of either agent is a decreasing function of the sum of the processing times of the jobs already scheduled in a given schedule. The goal is to seek for an optimal schedule that minimizes the total weighted completion time of the first agent, subject to no tardy job for the second agent. We first provide a branch-and-bound method to solve the problem. We then develop an approach that combines genetic algorithm and simulated annealing to seek for approximate solutions for the problem. We carry on extensive computational tests to assess the performance of the proposed algorithms.     

A branch-and-bound algorithm with fuzzy inference for a permutation flowshop scheduling problem

This paper considers an m-machine permutation flowshop scheduling problem of minimizing the makespan. This classical scheduling problem is still important in modern manufacturing systems, and is well known to be intractable (i.e., NP-hard). In fact branch-and-bound algorithms developed so far for this problem have not come to solve large scale problem instances with over a hundred jobs. In order to improve the performance of branch-and-bound algorithms this paper proposes a new dominance relation by which the search load could be reduced, and notices that it is based on a sufficient precondition. This suggests that the dominance relation holds with high possibility even if the precondition approximately holds, thus being more realistic. The branch-and-bound algorithm proposed here takes advantage of this possibility for obtaining an optimal solution as early as possible in the branch-and-bound search. For this purpose this paper utilizes membership functions in the context of the fuzzy inference. Extensive numerical experiments that were executed through Monte Carlo simulations and benchmark tests show that the developed branch-and-bound algorithm can solve 3-machine problem instances with up to 1000 jobs with probability of over 99%, and 4-machine ones with up to 900 jobs with over 97%.     

On scheduling around large restrictive common due windows

This paper deals with the problem of scheduling a number of jobs on a single machine around a large, restrictive common due window. We consider individual earliness and tardiness penalties for the jobs. The objective is to find an optimal schedule which jointly minimizes the sum of the earliness and tardiness penalties. This problem is intractable and hence no efficient procedure for solving large instances is expected to be found. For this reason we first introduced a mapping of the problem which takes advantage of the structural properties inherent to optimal solutions. Secondly we solved the problem under study by using this mapping and applying three meta-heuristics, namely evolutionary strategy, simulated annealing and threshold accepting. To validate the quality of these approaches, altogether 250 benchmark problems with different window sizes and positions of up to 200 jobs are examined. Furthermore small instances are solved to optimality by a mixed integer programming formulation.     

Robust berth scheduling with uncertain vessel delay and handling time

In container terminals, the actual arrival time and handling time of a vessel often deviate from the scheduled ones. Being the input to yard space allocation and crane planning, berth allocation is one of the most important activities in container terminals. Any change of berth plan may lead to significant changes of other operations, deteriorating the reliability and efficiency of terminal operations. In this paper, we study a robust berth allocation problem (RBAP) which explicitly considers the uncertainty of vessel arrival delay and handling time. Time buffers are inserted between the vessels occupying the same berthing location to give room for uncertain delays. Using total departure delay of vessels as the service measure and the length of buffer time as the robustness measure, we formulate RBAP to balance the service level and plan robustness. Based on the properties of the optimal solution, we develop a robust berth scheduling algorithm (RBSA) that integrates simulated annealing and branch-and-bound algorithm. To evaluate our model and algorithm design, we conduct computational study to show the effectiveness of the proposed RBSA algorithm, and use simulation to validate the robustness and service level of the RBAP formulation.     

An efficient grouping genetic algorithm for U-shaped assembly line balancing problems with maximizing production rate

U-type assembly line is one of the important tools that may increase companies’ production efficiency. In this study, two different modeling approaches proposed for the assembly line balancing problems have been used in modeling type-II U-line balancing problems, and the performances of these models have been compared with each other. It has been shown that using mathematical formulations to solve medium and large size problem instances is impractical since the problem is NP-hard. Therefore, a grouping genetic and simulated annealing algorithms have been developed, and a particle swarm optimization algorithm is adapted to compare with the proposed methods. A special crossover operator that always obtains feasible offspring has been suggested for the proposed grouping genetic algorithm. Furthermore, a local search procedure based on problem-specific knowledge was applied to increase the intensification of the algorithm. A set of well-known benchmark instances was solved to evaluate the effectiveness of the proposed and existing methods. Results showed that while the mathematical formulations can only be used to solve small size instances, metaheuristics can obtain high quality solutions for all size problem instances within acceptable CPU times. Moreover, grouping genetic algorithm has been found to be superior to the other methods according to the number of optimal solutions, or deviations from the lower bound values.     

Optimal berth allocation and time-invariant quay crane assignment in container terminals

Due to the dramatic increase in the world’s container traffic, the efficient management of operations in seaport container terminals has become a crucial issue. In this work, we focus on the integrated planning of the following problems faced at container terminals: berth allocation, quay crane assignment (number), and quay crane assignment (specific). First, we formulate a new binary integer linear program for the integrated solution of the berth allocation and quay crane assignment (number) problems called BACAP. Then we extend it by incorporating the quay crane assignment (specific) problem as well, which is named BACASP. Computational experiments performed on problem instances of various sizes indicate that the model for BACAP is very efficient and even large instances up to 60 vessels can be solved to optimality. Unfortunately, this is not the case for BACASP. Therefore, to be able to solve large instances, we present a necessary and sufficient condition for generating an optimal solution of BACASP from an optimal solution of BACAP using a post-processing algorithm. In case this condition is not satisfied, we make use of a cutting plane algorithm which solves BACAP repeatedly by adding cuts generated from the optimal solutions until the aforementioned condition holds. This method proves to be viable and enables us to solve large BACASP instances as well. To the best of our knowledge, these are the largest instances that can be solved to optimality for this difficult problem, which makes our work applicable to realistic problems.     

Total tardiness minimization in permutation flowshop with deterioration consideration

In this paper, we consider a permutation flowshop scheduling problem with deteriorating jobs. The objective is to minimize the total tardiness of all jobs. A branch-and-bound algorithm incorporating with a dominance property and a lower bound is developed. Furthermore, two metaheuristic algorithms, the simulated annealing algorithm, and the particle swarm optimization method, are proposed. Finally, computational studies are given.     

Optimal stochastic single-machine-tardiness scheduling by stochastic branch-and-bound

A stochastic branch-and-bound technique for the solution of stochastic single-machine-tardiness problems with job weights is presented. The technique relies on partitioning the solution space and estimating lower and upper bounds by sampling. For the lower bound estimation, two different types of sampling (“within” and “without” the minimization) are combined. Convergence to the optimal solution (with probability one) can be demonstrated. The approach is generalizable to other discrete stochastic optimization problems. In computational experiments with the single-machine-tardiness problem, the technique worked well for problem instances with a relatively small number of jobs; due to the enormous complexity of the problem, only approximate solutions can be expected for a larger number of jobs. Furthermore, a general precedence rule for the single-machine scheduling of jobs with uncertain processing times has been derived, essentially saying that “safe” jobs are to be scheduled before “unsafe” jobs.     

A Simulated Annealing Approach to Bicriteria Scheduling Problems on a Single Machine

In this paper, we apply a simulated annealing approach to two bicriteria scheduling problems on a single machine. The first problem is the strongly NP-hard problem of minimizing total flowtime and maximum earliness. The second one is the NP-hard problem of minimizing total flowtime and number of tardy jobs. We experiment on different neighbourhood structures as well as other parameters of the simulated annealing approach to improve its performance. Our computational experiments show that the developed approach yields solutions that are very close to lower bounds and hence very close to the optimal solutions of their corresponding problems for the minimization of total flowtime and maximum earliness. For the minimization of total flowtime and number tardy, our experiments show that the simulated annealing approach yields results that are superior to randomly generated schedules.     

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.     

Two-agent scheduling with position-based deteriorating jobs and learning effects

Scheduling with deteriorating jobs and learning effects has been widely studied. However, multi-agent scheduling with simultaneous considerations of deteriorating jobs and learning effects has hardly been considered until now. In view of this, we consider a two-agent single-machine scheduling problem involving deteriorating jobs and learning effects simultaneously. In the proposed model, given a schedule, we assume that the actual processing time of a job of the first agent is a function of position-based learning while the actual processing time of a job of the second agent is a function of position-based deterioration. The objective is to minimize the total weighted completion time of the jobs of the first agent with the restriction that no tardy job is allowed for the second agent. We develop a branch-and-bound and several simulated annealing algorithms to solve the problem. Computational results show that the proposed algorithms are efficient in producing near-optimal solutions.     

Solving binary cutting stock problems by column generation and branch-and-bound

We present an algorithm for the binary cutting stock problem that employs both column generation and branch-and-bound to obtain optimal integer solutions. We formulate a branching rule that can be incorporated into the subproblem to allow column generation at any node in the branch-and-bound tree. Implementation details and computational experience are discussed.This research was supported by NSF and AFOSR grant DDM-9115768     

Minimizing the sum of maximum earliness and maximum tardiness in the single-machine scheduling problem with sequence-dependent setup time

This paper considers the problem of scheduling a given number of jobs on a single machine to minimize the sum of maximum earliness and maximum tardiness when sequence-dependent setup times exist (1∣ST _sd ∣ET_max). In this paper, an optimal branch-and-bound algorithm is developed that involves the implementation of lower and upper bounding procedures as well as three dominance rules. For solving problems containing large numbers of jobs, a polynomial time-bounded heuristic algorithm is also proposed. Computational experiments demonstrate the effectiveness of the bounding and dominance rules in achieving optimal solutions in more than 97% of the instances.     

An exact method for scheduling a yard crane

This paper studies an operational problem arising at a container terminal, consisting of scheduling a yard crane to carry out a set of container storage and retrieval requests in a single container block. The objective is to minimize the total travel time of the crane to carry out all requests. The block has multiple input and output (I/O) points located at both the seaside and the landside. The crane must move retrieval containers from the block to the I/O points, and must move storage containers from the I/O points to the block. The problem is modeled as a continuous time integer programming model and the complexity is proven. We use intrinsic properties of the problem to propose a two-phase solution method to optimally solve the problem. In the first phase, we develop a merging algorithm which tries to patch subtours of an optimal solution of an assignment problem relaxation of the problem and obtain a complete crane tour without adding extra travel time to the optimal objective value of the relaxed problem. The algorithm requires common I/O points to patch subtours. This is efficient and often results in obtaining an optimal solution of the problem. If an optimal solution has not been obtained, the solution of the first phase is embedded in the second phase where a branch-and-bound algorithm is used to find an optimal solution. The numerical results show that the proposed method can quickly obtain an optimal solution of the problem. Compared to the random and Nearest Neighbor heuristics, the total travel time is on average reduced by more than 30% and 14%, respectively. We also validate the solution method at a terminal.     

A hybrid genetic algorithm for an identical parallel-machine problem with maintenance activity

The scheduling of maintenance activities has been extensively studied, with most studies focusing on single-machine problems. In real-world applications, however, multiple machines or assembly lines process numerous jobs simultaneously. In this paper, we study a parallel-machine scheduling problem in which the objective is to minimize the total tardiness given that there is a maintenance activity on each machine. We develop a branch-and-bound algorithm to solve the problem with a small problem size. In addition, we propose a hybrid genetic algorithm to obtain the approximate solutions when the number of jobs is large. The performance of the proposed algorithms is evaluated based mainly on computational results.     

Improved MILP models for two-machine flowshop with batch processing machines

In this paper, we consider the problem of scheduling jobs in a flowshop with two batch processing machines such that the makespan is minimized. Batch processing machines are frequently encountered in many industrial environments such as heat treatment operations in a steel foundry and chemical processes performed in tanks or kilns. Improved Mixed Integer Linear Programming (MILP) models are presented for the flowshop problem with unlimited or zero intermediate storage. An MILP-based heuristic is also developed for the problem. Computational experiments show that the new MILP models can significantly improve the original ones. Also, the heuristic can obtain the optimal solutions for all the test problem instances.     

An Almost Optimal Heuristic for Preemptive C max Scheduling of Dependent Tasks on Parallel Identical Machines

We consider the problem of scheduling preemptable, dependent tasks on parallel, identical machines to minimize the makespan. The computational complexity of this problem remains open if the number of machines is fixed and larger than 2. The aim of this paper is to compare two heuristic algorithms on a basis of a computational experiment. The solutions generated by the heuristics are compared with optimal solutions obtained by a branch-and-bound algorithm. Computational results show that the heuristic based on node ordering finds optimal schedules for 99.9% of instances with the maximum relative deviation from optimum of 4.8%.     

带准备时间的单机指数时间学习效应排序问题

研究带有准备时间的单机学习效应模型,其中工件加工时间具有指数时间学习效应,即工件的实际加工时间是已经排好的工件加工时间的指数函数。学习效应模型考虑工件的实际加工时间同时依赖于工件本身的加工时间和已加工工件的累计加工时间,目标函数为最小化总完工时间。这个问题是NP-难的,提出了一个数学规划模型来求解该问题的最优解。通过分析几个优势性质和下界,提出分支定界算法来求解此问题,并设计启发式算法改进分支定界算法的上界值。通过仿真实验验证了分支定界算法在求解质量和时间方面的有效性。