Explore the vast range of titles available.

In vehicle routing problems (VRPs) the decisions to be taken concern the assignment of customers to vehicles and the sequencing of the customers assigned to each vehicle. Additional decisions may need to be jointly taken, depending on the specific problem setting. In this paper, after discussing the different kinds of decisions taken in different classes of VRPs, the class where the decision about when the routes start from the depot has to be taken is considered and the related literature is reviewed. This class of problems, that we call VRPs over time, includes the periodic routing problems, the inventory routing problems, the vehicle routing problems with release dates, and the multi-trip vehicle routing problems.

In vehicle routing problems (VRPs) the decisions to be taken concern the assignment of customers to vehicles and the sequencing of the customers assigned to each vehicle. Additional decisions may need to be jointly taken, depending on the specific problem setting. In this paper, after discussing the different kinds of decisions taken in different classes of VRPs, the class where the decision about when the routes start from the depot has to be taken is considered and the related literature is reviewed. This class of problems, that we call VRPs over time, includes the periodic routing problems, the inventory routing problems, the vehicle routing problems with release dates, and the multi-trip vehicle routing problems.

Flexible job shop scheduling problem (FJSSP) is generalization of job shop scheduling problem (JSSP), in which an operation may be processed on more than one machine each of which has the same function. Most previous researches on FJSSP assumed that all jobs to be processed are available at the beginning of scheduling horizon. The assumption, however, is always violated in practical industries because jobs usually arrive over time and can not be predicted before their arrivals. In the paper, dynamic flexible job shop scheduling problem (DFJSSP) with job release dates is studied. A heuristic is proposed to implement reactive scheduling for the dynamic scheduling problem. An approach based on gene expression programming (GEP) is also proposed which automatically constructs reactive scheduling policies for the dynamic scheduling. In order to evaluate the performance of the reactive scheduling policies constructed by the proposed GEP-based approach under a variety of processing conditions three factors, such as the shop utilization, due date tightness, problem flexibility, are considered in the simulation experiments. The scheduling performance measure considered in the simulation is the minimization of makespan, mean flowtime and mean tardiness, respectively. The results show that GEP-based approach can construct more efficient reactive scheduling policies for DFJSSP with job release dates under a big range of processing conditions and performance measures in the comparison with previous approaches.

We study several competitive two-agent scheduling problems with release dates and preemption on a single machine, where the scheduling criterion of the first agent is regular and of the sum-form and the scheduling criterion of the second criterion is regular and of the max-form or the weighted number of tardy jobs. Two variants of the problems are investigated. One is the restricted version, in which the goal is to find a feasible schedule so that the objective value of the first agent is minimized subject to the restriction that the objective value of the second agent does not exceed a given threshold value. The other one is the Pareto version, in which the goal is to find all the Pareto-optimal points and their corresponding Pareto-optimal schedules. We design polynomial-time and pseudo-polynomial-time algorithms for each of the considered problems.

We study the single-machine scheduling with maintenance intervals under preemptive pattern and resumable pattern, respectively, to minimize the total weighted late work and the weighted number of tardy jobs, respectively, where each job has a release date and a due date. According to the different combinations of the two scheduling patterns and the two scheduling criteria, six scheduling problems (including two Pareto-scheduling problems) are studied in this paper. We show that by modifying the release dates and the due dates, the six problems can be reduced to their corresponding scheduling problems without maintenance intervals in quasi-linear time. As a consequence, complexity results of our problems can be directly obtained from the known results in the literature. In particular, for the problem under resumable pattern to minimize the total weighted late work with all the jobs being released at time 0, an O(mn2P)-time algorithm was presented in the literature, where m is the number of maintenance intervals, n is the number of jobs, and P is the total processing time of the jobs; and our research shows that the same problem is solvable in O(n2P+mlogm) time, improving this known result.

In this paper we consider three machine scheduling problems with the special feature that jobs may be rejected at a certain penalty. There are n jobs which are characterized by a release date, a processing time and a penalty. Each job is either accepted and then processed by one machine, or rejected and then a rejection penalty is paid. The objective is to minimize the maximum completion time of all accepted job plus the total penalties of all rejected jobs. When jobs have identical release dates, we present a ( 32-12m )-approximation algorithm for the parallel machine problem. When jobs have general release dates, we propose a 43 -approximation algorithm for the single machine problem and a ( 1+max0.618,1-1m )-approximation algorithm for the parallel machine problem, respectively.

We study various single machine scheduling problems with two competing agents, unit processing times and arbitrary integer release dates. The problems differ by the scheduling criterion used by each of the two agents, and by the variant of the bicriteria problem that has to be solved. We prove that when the scheduling criterion of either one of the two agents is of a max-type, then all considered variants of the bicriteria problem are solvable in polynomial time. However, when the two agents have a sum-type of scheduling criterion, several variants of the bicriteria problem become NP -hard.

In this paper we study a parallel machine scheduling model with different job release dates, where each job is either accepted and processed by a machine at or after its release date, or it is rejected and a certain penalty cost is paid. The objective is to minimize the makespan of the accepted job plus the total penalty of all rejected jobs. The scheduling problem is NP-hard in the strong sense. Zhang and Lu (4OR A Q J Oper Res 14:165–172, 2016 ) have proposed a 2-approximation for the problem, and a fully polynomial time approximation scheme (FPTAS) for the special case when the number of machines m is fixed. In this paper we present an improved 2-approximation and a polynomial time approximation scheme for the problem. We also propose an improved FPTAS for the case when m is fixed.

In this research, we consider the problem of scheduling n jobs on m unrelated parallel machines with release dates to minimize makespan, total weighted completion time, and total weighted tardiness, individually. The problem is NP-hard in the strong sense. We develop several mixed integer programming models for these scheduling problems to find the optimal solutions for small problem instances. We also propose several dispatching rules to find good solutions quickly for large problem instances. We compare our proposed dispatching rules with other existing dispatching rules. Computational results show that the proposed dispatching rules outperform other existing dispatching rules for problem instances of all sizes.

We consider bi-criteria scheduling problems on a single machine with release dates and rejections and both the makespan and the total rejection cost have to be minimized. We consider three scenarios: (1) minimize the sum of the two objectives: makespan and total rejection cost, (2) minimize the makespan subject to a bound on the total rejection cost and (3) minimize the total rejection cost subject to a bound on the makespan. We summarize the results obtained in the literature and provide for several cases improved approximation algorithms and FPTASs.