Synchronizing production and air transportation scheduling using mathematical programming models

Traditional scheduling problems assume that there are always infinitely many resources for delivering finished jobs to their destinations, and no time is needed for their transportation, so that finished products can be transported to customers without delay. So, for coordination of these two different activities in the implementation of a supply chain solution, we studied the problem of synchronizing production and air transportation scheduling using mathematical programming models. The overall problem is decomposed into two sub-problems, which consists of air transportation allocation problem and a single machine scheduling problem which they are considered together. We have taken into consideration different constraints and assumptions in our modeling such as special flights, delivery tardiness and no delivery tardiness. For these purposes, a variety of models have been proposed to minimize supply chain total cost which encompass transportation, makespan, delivery earliness tardiness and departure time earliness tardiness costs.     

A heuristic approach to a single stage assembly problem with transportation allocation

Determining assembly scheduling and transportation allocation are two practical problems that industries face, such as the electronics and health products industries. Problems associated with assembly scheduling mainly focus on how to determine the orders’ processing sequence on the assembly line in order to minimize the waiting times before they are flown to their destinations. Problems associated with transportation allocation arise in the system of assigning processed orders to transport modes with the purpose of minimizing penalties from earliness and tardiness. To minimize overall delivery costs, businesses should decide on assembly scheduling and transportation allocation decision simultaneously. However, since simultaneously making these two decisions is not an easy task, most of the works done on them usually deal with these two problems separately. Apart from previous works, this paper establishes a mixed integer programming model that deals with these problems simultaneously. Due to the computational complexity of the problem, this paper develops a hybrid heuristic algorithm to solve this problem, and we evaluate the performance of the presented heuristic algorithm with the well-known GAMS/BARON and Lingo commercial software, which tests the heuristic algorithm on randomly-generated problems. The presented heuristic algorithm is shown to perform well compared with well-known commercial software.     

Single machine scheduling with batch deliveries

The single machine batch scheduling problem is studied. The jobs in a batch are delivered to the customer together upon the completion time of the last job in the batch. The earliness of a job is defined as the difference between the delivery time of the batch to which it belongs and its completion time. The objective is to minimize the sum of the batch delivery and job earliness penalties. A relation between this problem and the parallel machine scheduling problem is identified. This enables the establishment of complexity results and algorithms for the former problem based on known results for the latter problem.     

Due-window assignment with identical jobs on parallel uniform machines

A scheduling problem with a common due-window, earliness and tardiness costs, and identical processing time jobs is studied. We focus on the setting of both (i) job-dependent earliness/tardiness job weights and (ii) parallel uniform machines. The objective is to find the job allocation to the machines and the job schedule, such that the total weighted earliness and tardiness cost is minimized. We study both cases of a non-restrictive (i.e. sufficiently late), and a restrictive due-window. For a given number of machines, the solutions of the problems studied here are obtained in polynomial time in the number of jobs.     

Common due window size and location determination in a single machine scheduling problem

We consider a single machine static and deterministic scheduling problem in which jobs have a common due window. Jobs completed within the window incur no penalties, other jobs incur either earliness or tardiness penalties. The objective is to find the optimal size and location of the window as well as an optimal sequence to minimise a cost function based on earliness, tardiness, window size, and window location. We propose an O(n log n) algorithm to solve the problem.     

Single Machine Earliness-Tardiness Scheduling Problems Using the Equal—Slack Rule

The purpose of this paper is to analyse a special case of the non-pre-emptive single machine scheduling problem where the distinct due dates for each job are related to processing times according to the Equal–Slack rule. The scheduling objective is to minimize the sum of earliness and tardiness penalties. After determining some properties of the problem, the unrestricted case is shown to be equivalent to a polynomial time solvable problem, whereas the restricted case is shown to be NP-hard, and suggestions are made for further research.     

Determination of common due window location in a single machine scheduling problem

We consider the static deterministic single machine scheduling problem in which all jobs have a common due window. Jobs that are completed within the window incur no penalty. The objective is to find the optimal sequence and the optimal common due window location given that the due window size is a problem parameter such that the weighted sum of earliness, tardiness, and due window location penalties is minimized. We propose an O(n log n) algorithm to solve the problem. We also consider two special cases for which simple solutions can be obtained.     

Multiobjective evolutionary algorithms to identify highly autocorrelated areas: the case of spatial distribution in financially compromised farms

In this paper, we address the optimal batch sizing and just-in-time scheduling problem where upper and lower bounds on the size of the batches are imposed. The objective is to find a feasible schedule that minimizes the sum of the weighted earliness and tardiness penalties as well as the setup costs, which involves the cost of creating a new batch. We present some structural properties of the optimal schedules and describe solving algorithms for the single machine problem.     

Scheduling with a due-window for acceptable lead-times

Due-dates are often determined during sales negotiations in two stages: (i) in the pre-sale stage, the customer provides a time interval (due-window) of his acceptable due-dates, (ii) in the second stage, the parties agree on the delivery penalties. Thus, the contract reflects penalties of both parts of the sales negotiations: earliness/tardiness penalties of the due-dates (as a function of the deviation from the agreed upon due-window), and earliness/tardiness penalties of the actual delivery times (as a function of the deviation from the due-dates). We model this setting of a two-stage negotiation on a single machine, and reduce the problem to a well-known setting of minimizing the weighted earliness/tardiness with a given (fixed) due-window. We adopt (and correct) a pseudo-polynomial dynamic programming algorithm for this NP-hard problem. The algorithm is extended to a setting of parallel identical machines, verifying that this case remains NP-hard in the ordinary sense. Moreover, an efficient greedy heuristic and a tight lower bound are introduced and tested. Extremely small optimality gaps are obtained in our numerical tests.     

Single machine scheduling with symmetric earliness and tardiness penalties

This research focuses on scheduling jobs with varying processing times and distinct due dates on a single machine subject to earliness and tardiness penalties. Hence, this work will find application in a just-in-time (JIT) production environment. The scheduling problem is formulated as a 0–1 linear integer program with three sets of constraints, where the objective is to minimize the sum of the absolute deviations between job completion times and their respective due dates. The first two sets of constraints are equivalent to the supply and demand constraints of an assignment problem. The third set, which represents the process time non-overlap constraints, is relaxed to form the Lagrangian dual problem. The dual problem is then solved using the subgradient algorithm. Efficient heuristics have also been developed in this work to yield initial primal feasible solutions and to convert primal infeasible solutions to feasibility. The computational results show that the relative deviation from optimality obtained by the subgradient algorithm is less than 3% for problem sizes varying from 10 to 100 jobs.     

Scheduling a single machine to minimize earliness penalties subject to the SLK due-date determination method

This paper considers a single machine scheduling problem. There are n jobs to be processed on a single machine. The problem is to minimize total earliness penalties subject to no tardy jobs. The problem is NP-complete if the due-dates are arbitrary. We study the problem when the due-dates are determined by the equal slack (SLK) method. Two special cases of the problem are solved in polynomial time. The first one is the problem with equally weighted monotonous penalty objective function. The second one is the problem with weighted linear penalty objective function.     

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.     

The Coordination of Scheduling and Batch Deliveries

This paper considers several scheduling problems where deliveries are made in batches with each batch delivered to the customer in a single shipment. Various scheduling costs, which are based on the delivery times of the jobs, are considered. The objective is to minimize the scheduling cost plus the delivery cost, and both single and parallel machine environments are considered. For many combinations of these, we either provide efficient algorithms that minimize total cost or show that the problem is intractable. Our work has implications for the coordination of scheduling with batch delivery decisions to improve customer service.     

The one-machine just-in-time scheduling problem with preemption

This paper investigates the notion of preemption in scheduling, with earliness and tardiness penalties. Starting from the observation that the classical cost model where penalties only depend on completion times does not capture the just-in-time philosophy, we introduce a new model where the earliness costs depend on the start times of the jobs. To solve this problem, we propose an efficient representation of dominant schedules, and a polynomial algorithm to compute the best schedule for a given representation. Both a local search algorithm and a branch-and-bound procedure are then derived. Experiments finally show that the gap between our upper bound and the optimum is very small.     

一个双目标单机调度问题及其几个多项式可解情形

研究了一个双目标单机调度问题及其几个多项式可解的情形。问题的主目标是延误工件数最小,在此条件下,最小化各工件加权提前期的总和,由于该问题是NP一难的,故研究求解它的一个启发式算法及问题的几个多项式可解的特殊情形。     

Soft due window assignment and scheduling of unit-time jobs on parallel machines

We study problems of scheduling n unit-time jobs on m identical parallel machines, in which a common due window has to be assigned to all jobs. If a job is completed within the due window, then no scheduling cost incurs. Otherwise, a job-dependent earliness or tardiness cost incurs. The job completion times, the due window location and the size are integer valued decision variables. The objective is to find a job schedule as well as the location and the size of the due window such that a weighted sum or maximum of costs associated with job earliness, job tardiness and due window location and size is minimized. We establish properties of optimal solutions of these min-sum and min-max problems and reduce them to min-sum (traditional) or min-max (bottleneck) assignment problems solvable in O(n ⁵/m ²) and O(n ^4.5log^0.5 n/m ²) time, respectively. More efficient solution procedures are given for the case in which the due window size cost does not exceed the due window start time cost, the single machine case, the case of proportional earliness and tardiness costs and the case of equal earliness and tardiness costs.     

Due-date assignment and single machine scheduling with deteriorating jobs

We study a scheduling problem with deteriorating jobs, that is, jobs whose processing times are an increasing function of their start times. We consider the case of a single machine and linear job-independent deterioration. The problem is to determine an optimal combination of the due-date and schedule so as to minimize the sum of due-date, earliness and tardiness penalties. We give an O(n log n) time algorithm to solve this problem.     

Due-date assignment on uniform machines

The classical weighted minsum scheduling and due-date assignment problem (with earliness, tardiness and due-date costs) was shown to be polynomially solvable on a single machine, more than two decades ago. Later, it was shown to have a polynomial time solution in the case of identical processing time jobs and parallel identical machines. We extend the latter setting to parallel uniform machines. We show that the two-machine case is solved in constant time. Furthermore, the problem remains polynomially solvable for a given (fixed) number of machines.     

Minmax scheduling with job-classes and earliness–tardiness costs

We address scheduling problems with job-dependent due-dates and general (possibly nonlinear and asymmetric) earliness and tardiness costs. The number of distinct due-dates is substantially smaller than the number of jobs, thus jobs are partitioned to classes, where all jobs of a given class share a common due-date. We consider the settings of a single machine and parallel identical machines. Our objective is of a minmax type, i.e., we seek a schedule that minimizes the maximum earliness/tardiness cost among all jobs.     

Minimizing total earliness and tardiness on re-entrant batch processing machine with time windows

The time window (TW) generalizes the concept of due date. The semiconductor wafer fabrication system is currently one of the most complex production processes, which has typical re-entrant batch processing machine (RBPM). RBPM is a bottleneck. This paper addresses a scheduling of RBPM with job-dependent TWs. According to a general modelling, an improved and new job-family-oriented modelling of the decomposition method that is based on the slack mixed integer linear programming is proposed. First, the complicated scheduling problem of RBPM is divided into sub-problems, which are executed circularly. Then, each one consists of updating, sequencing and dispatching. The objective is to minimize the total earliness and tardiness for job-dependent TWs. In order to evaluate the proposed modelling, the experiments are implemented on the real-time scheduling simulation platform and optimization toolkit ILOG CPLEX. The results show that the improved modelling obtains better solutions in less computation time.