Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries for multiple customers in supply chains

In this paper, an integrated due date assignment and production and batch delivery scheduling problem for make-to-order production system and multiple customers is addressed. Consider a supply chain scheduling problem in which n orders (jobs) have to be scheduled on a single machine and delivered to K customers or to other machines for further processing in batches. A common due date is assigned to all the jobs of each customer and the number of jobs in delivery batches is constrained by the batch size. The objective is to minimize the sum of the total weighted number of tardy jobs, the total due date assignment costs and the total batch delivery costs. The problem is NP-hard. We formulate the problem as an Integer Programming (IP) model. Also, in this paper, a Heuristic Algorithm (HA) and a Branch and Bound (B&B) method for solving this problem are presented. Computational tests are used to demonstrate the efficiency of the developed methods.     

Short-term work scheduling with job assignment flexibility for a multi-fleet transport system

In recent years, planning and management of operations of transportation companies has become increasingly complex as tighter financial constraints affect the ability to respond to changing demands for travel. This paper investigates how a firm can reduce its total labor cost, enhance the flexibility of its operations and improve worker productivity and utilization by determining the right mix of jobs in work schedules. Using a method we have developed to generate low cost work schedules for bus drivers of an inter-city transport system in India, we study the changes in worker productivity and utilization when a mix of primary and secondary jobs is built in work schedules. We also investigate other factors that can strongly influence worker productivity and utilization such as the amount of overtime in work schedules, the level of job assignment flexibility, and staff size. Test results and discussions of managerial implications are presented.     

Analysis of job assignment with batch arrivals among heterogeneous servers

We revisit the problem of job assignment to multiple heterogeneous servers in parallel. The system under consideration, however, has a few unique features. Specifically, repair jobs arrive to the queueing system in batches according to a Poisson process. In addition, servers are heterogeneous and the service time distributions of the individual servers are general. The objective is to optimally assign each job within a batch arrival to minimize the long-run average number of jobs in the entire system. We focus on the class of static assignment policies where jobs are routed to servers upon arrival according to pre-determined probabilities. We solve the model analytically and derive the structural properties of the optimal static assignment. We show that when the traffic is below a certain threshold, it is better to not assign any jobs to slower servers. As traffic increases (either due to an increase in job arrival rate or batch size), more slower servers will be utilized. We give an explicit formula for computing the threshold. Finally we compare and evaluate the performance of the static assignment policy to two dynamic policies, specifically the shortest expected completion policy and the shortest queue policy.     

Single-machine due window assignment and scheduling with a common flow allowance and controllable job processing time

In this paper, we consider single-machine due window assignment and scheduling with a common flow allowance and controllable job processing times, subject to unlimited or limited resource availability. Due window assignment with a common flow allowance means that each job has a job-dependent due window, the starting time and completion time of which are equal to its actual processing time plus the job-independent parameters q₁ and q₂, respectively, which are common to all the jobs. The processing time of each job is either a linear or a convex function of the amount of a common continuously divisible resource allocated to the job. We study five versions of the problem that differ in terms of the objective function and processing time function being used. We provide structural properties of the optimal schedules and polynomial-time solution algorithms for the considered problems.     

Flowshop scheduling problem to minimize total completion time with random and bounded processing times

The flowshop scheduling problems with n jobs processed on two or three machines, and with two jobs processed on k machines are addressed where jobs have random and bounded processing times. The probability distributions of random processing times are unknown, and only the lower and upper bounds of processing times are given before scheduling. In such cases, there may not exist a unique schedule that remains optimal for all feasible realizations of the processing times, and therefore, a set of schedules has to be considered which dominates all other schedules for the given criterion. We obtain sufficient conditions when transposition of two jobs minimizes total completion time for the cases of two and three machines. The geometrical approach is utilized for flowshop problem with two jobs and k machines.     

Two-machine flowshop scheduling to minimize the number of tardy jobs

We consider the two-machine flowshop problem with the objective of minimizing the total number of tardy jobs. Since this problem is known to be strongly NP-hard, algorithms are described for four polynomially solvable special cases. In addition, several heuristic algorithms are developed to find optimal or near optimal schedules. Results of computational tests in solving problems up to 60 jobs are reported and directions for future research are provided.     

A rank-based approach to the sequential selection and assignment problem

In the classical sequential assignment problem, “machines” are to be allocated sequentially to “jobs” so as to maximize the expected total return, where the return from an allocation of job j to machine k is the product of the value x_j of the job and the weight p_k of the machine. The set of m machines and their weights are given ahead of time, but n jobs arrive in sequential order and their values are usually treated as independent, identically distributed random variables from a known univariate probability distribution with known parameter values. In the paper, we consider a rank-based version of the sequential selection and assignment problem that minimizes the sum of weighted ranks of jobs and machines. The so-called “secretary problem” is shown to be a special case of our sequential assignment problem (i.e., m = 1). Due to its distribution-free property, our rank-based assignment strategy can be successfully applied to various managerial decision problems such as machine scheduling, job interview, kidney allocations for transplant, and emergency evacuation plan of patients in a mass-casualty situation.     

A column generation based decomposition algorithm for a parallel machine just-in-time scheduling problem

We propose a column generation based exact decomposition algorithm for the problem of scheduling n jobs with an unrestrictively large common due date on m identical parallel machines to minimize total weighted earliness and tardiness. We first formulate the problem as an integer program, then reformulate it, using Dantzig–Wolfe decomposition, as a set partitioning problem with side constraints. Based on this set partitioning formulation, a branch and bound exact solution algorithm is developed for the problem. In the branch and bound tree, each node is the linear relaxation problem of a set partitioning problem with side constraints. This linear relaxation problem is solved by column generation approach where columns represent partial schedules on single machines and are generated by solving two single machine subproblems. Our computational results show that this decomposition algorithm is capable of solving problems with up to 60 jobs in reasonable cpu time.     

An extended assignment problem considering multiple inputs and outputs

The existing assignment problems for assigning n jobs to n individuals are limited to the considerations of cost or profit incurred by each possible assignment. However, in real applications, various inputs and outputs are usually concerned in an assignment problem, such as a general decision-making problem. This paper develops a procedure for resolving assignment problems with multiple incommensurate inputs and outputs for each possible assignment. The concept of the relative efficiency in using various resources, instead of cost or profit, is adopted for each possible assignment of the problem. Data envelopment analysis (DEA) is employed in this paper to measure the efficiency of one assignment relative to that of the others according to a set of decision-making units. A composite efficiency index, consisting of two kinds of relative efficiencies under different comparison bases, is defined to serve as the performance measurement of each possible assignment in the problem formulation. A mathematical programming model for the extended assignment problem is proposed, which is then expressed as a classical integer linear programming model to determine the assignments with the maximum efficiency. A numerical example is used to demonstrate the approach.     

Approximation schemes for parallel machine scheduling with availability constraints

We investigate the problems of scheduling n weighted jobs to m parallel machines with availability constraints. We consider two different models of availability constraints: the preventive model, in which the unavailability is due to preventive machine maintenance, and the fixed job model, in which the unavailability is due to a priori assignment of some of the n jobs to certain machines at certain times. Both models have applications such as turnaround scheduling or overlay computing. In both models, the objective is to minimize the total weighted completion time. We assume that m is a constant, and that the jobs are non-resumable.For the preventive model, it has been shown that there is no approximation algorithm if all machines have unavailable intervals even if w_i=p_i for all jobs. In this paper, we assume that there is one machine that is permanently available and that the processing time of each job is equal to its weight for all jobs. We develop the first polynomial-time approximation scheme (PTAS) when there is a constant number of unavailable intervals. One main feature of our algorithm is that the classification of large and small jobs is with respect to each individual interval, and thus not fixed. This classification allows us (1) to enumerate the assignments of large jobs efficiently; and (2) to move small jobs around without increasing the objective value too much, and thus derive our PTAS. Next, we show that there is no fully polynomial-time approximation scheme (FPTAS) in this case unless P=NP.For the fixed job model, it has been shown that if job weights are arbitrary then there is no constant approximation for a single machine with 2 fixed jobs or for two machines with one fixed job on each machine, unless P=NP. In this paper, we assume that the weight of a job is the same as its processing time for all jobs. We show that the PTAS for the preventive model can be extended to solve this problem when the number of fixed jobs and the number of machines are both constants.     

Single Stage Minimum Absolute Lateness Problem with a Common Due Date on Non-Identical Machines

In this paper we consider scheduling n single operation jobs with a common due date on m non-identical machines (in parallel) so as to minimize the sum of the absolute lateness. We reduce the problem to a transportation problem that can be solved by a polynomial time algorithm. Furthermore, we consider the problem in the case of identical machines and we give a heuristic algorithm to minimize makespan among all schedules that minimize the absolute lateness problem.     

A new approximation technique for resource‐allocation problems

We develop a rounding method based on random walks in polytopes, which leads to improved approximation algorithms and integrality gaps for several assignment problems that arise in resource allocation and scheduling. In particular, it generalizes the work of Shmoys and Tardos on the generalized assignment problem to the setting where some jobs can be dropped. New concentration bounds for random bipartite matching are developed as well.     

Power-aware scheduling of preemptable jobs on identical parallel processors to minimize makespan

This paper deals with power-aware scheduling of preemptable jobs on identical parallel processors to minimize schedule length when jobs are described by continuous, strictly concave functions relating their processing speed at time t to the amount of power allotted at the moment. Power is a continuous, doubly constrained resource, i.e. both: its availability at time t and consumption over scheduling horizon are constrained. Precedence constraints among jobs are represented by a task-on-arc graph. A methodology based on properties of optimal schedules is presented for solving the problem optimally for a given ordering of nodes in the graph. Heuristics for finding an ordering which leads to possibly short schedules are proposed and examined experimentally.     

Minimizing weighted earliness–tardiness and due-date cost with unit processing-time jobs

The classical single-machine scheduling and due-date assignment problem of Panwalker et al. [Panwalker, S.S., Smith, M.L., Seidmann, A., 1982. Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research 30(2) (1982) 391–399] is the following: All n jobs share a common due-date, which is to be determined. Jobs completed prior to or after the due-date are penalized according to a cost function which is linear and job-independent. The objective is to minimize the total earliness–tardiness and due-date cost. We study a generalized version of this problem in which: (i) the earliness and tardiness costs are allowed to be job dependent and asymmetric and (ii) jobs are processed on parallel identical machines. We focus on the case of unit processing-time jobs. The problem is shown to be solved in polynomial (O(n⁴)) time. Then we study the special case with no due-date cost (a classical problem known in the literature as TWET). We introduce an O(n³) solution for this case. Finally, we study the minmax version of the problem, (i.e., the objective is to minimize the largest cost incurred by any of the jobs), which is shown to be solved in polynomial time as well.     

A note on single-machine scheduling with job-dependent learning effects

Mosheiov and Sidney (2003) showed that the makespan minimization problem with job-dependent learning effects can be formulated as an assignment problem and solved in O(n³) time. We show that this problem can be solved in O(nlog n) time by sequencing the jobs according to the shortest processing time (SPT) order if we utilize the observation that the job-dependent learning rates are correlated with the level of sophistication of the jobs and assume that these rates are bounded from below. The optimality of the SPT sequence is also preserved when the job-dependent learning rates are inversely correlated with the level of sophistication of the jobs and bounded from above.     

基于重新排序的退化工件最小化总延误时间问题

考虑了错位限制下的含有退化工件的重新排序问题,即工件的实际加工时间看作是工件开工时间的线性函数．重新排序就是在原始工件已经按照某种规则使目标函数达到最优时有一新工件集到达,新工件的安排使得原始工件重新排序进而产生错位．研究了最大序列错位和总序列错位限制下的退化工件最小化总延误时间问题,其最优排序的结构性质是使得原始工件集和新工件集中的工件是按加工率αj非减的序列排列,基于此通过分阶段排序和动态规划方法给出了两个问题的多项式时间的最优算法．     

On the complexity of preemptive open-shop scheduling problems

The problem of preemptively scheduling a set of n independent jobs on an m-machine open shop is studied, and two results are obtained. The first indicates that constructing optimal flow-time schedules is NP-hard for m larger than two. The second result shows that the problem remains NP-hard for the two-processor case when all jobs must be completed by their respective deadlines.     

Multi-coloring and job-scheduling with assignment and incompatibility costs

Consider a scheduling problem (P) which consists of a set of jobs to be performed within a limited number of time periods. For each job, we know its duration as an integer number of time periods, and preemptions are allowed. The goal is to assign the required number of time periods to each job while minimizing the assignment and incompatibility costs. When a job is performed within a time period, an assignment cost is encountered, which depends on the involved job and on the considered time period. In addition, for some pairs of jobs, incompatibility costs are encountered if they are performed within common time periods. (P) can be seen as an extension of the multi-coloring problem. We propose various solution methods for (P) (namely a greedy algorithm, a descent method, a tabu search and a genetic local search), as well as an exact approach. All these methods are compared on different types of instances.     

Single-machine scheduling with common due-window assignment for deteriorating jobs

In this paper, we consider a single-machine common due-window assignment scheduling problem with deteriorating jobs. Jobs’ processing times are defined by function of their starting times and job-dependent deterioration rates that are related to jobs and are not all equal. The objective is to determine an optimal combination of sequence and common due-window location so as to minimize the weighted sum of earliness, tardiness and due-window location penalties. We propose an O(n² log n) time algorithm to solve the problem and discuss several instances to illustrate it.     

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.