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.     

Minimizing the weighted number of tardy jobs with due date assignment and capacity-constrained deliveries

We study a supply chain scheduling problem, where a common due date is assigned to all jobs and the number of jobs in delivery batches is constrained by the batch size. Our goal is to minimize the sum of the weighted number of tardy jobs, the due-date-assignment costs and the batch-delivery costs. We show that some well-known NP\mathcal{NP}-hard problems reduce to our problem. Then we propose a pseudo-polynomial algorithm for the problem, establishing that it is NP\mathcal{NP}-hard only in the ordinary sense. Finally, we convert the algorithm into an efficient fully polynomial time approximation scheme.     

Minimizing mean tardiness subject to unspecified minimum number tardy for a single machine

In this paper we propose a hybrid branch and bound algorithm for solving the problem of minimizing mean tardiness for a single machine problem subject to minimum number of tardy jobs. Although the minimum number of tardy jobs is known, the subset of tardy job is not known. The proposed algorithm uses traditional branch and bound scheme where lower bounds on mean tardiness are calculated coupled with using the information that the number of tardy jobs is known. It also uses an insertion algorithm which determines the optimal mean tardiness once the subset of tardy jobs is specified. An example is solved to illustrate the developed procedure.     

Fabrication scheduling on a single machine with due date constraints

There is a fabrication machine available for processing a set of jobs. Each job is associated with a due date and consists of two parts, one is common among all products and the other is unique to itself. The unique components are processed individually and the common parts are grouped into batches for processing. A constant setup time is incurred when each batch is formed. The completion time of a job is defined as the time when both of its unique and common components are completed. In this paper, we consider two different objectives. The first problem seeks to minimize the maximum tardiness, and the second problem is to minimize the number of tardy jobs. To minimize the maximum tardiness, we propose a dynamic programming algorithm that optimally solves the problem in polynomial time. Next, we show NP-hardness proof and design a pseudo-polynomial time dynamic programming algorithm for the problem of minimizing the number of tardy jobs.     

Single-machine batch scheduling minimizing weighted flow times and delivery costs

This paper addresses scheduling a set of jobs on a single machine for delivery in batches to one customer or to another machine for further processing. The problem is a natural extension of that of minimising the sum of weighted flow times, considering the possibility of delivering jobs in batches and introducing batch delivery costs. The scheduling objective adopted is that of minimising the sum of weighted flow times and delivery costs. The extended problem arises in the context of coordination between machine scheduling and a distribution system in a supply chain network. Structural properties of the problem are investigated and used to devise a branch-and-bound solution method. For the special case, when the maximum number of batches is fixed, the branch-and-bound scheme provided shows significant improvements over an existing dynamic-programming algorithm.     

Batch Delivery Scheduling on a Single Machine

The problem of partitioning a set of independent and simultaneously available jobs into batches and sequencing them for processing on a single machine is presented. Jobs in the same batch are to be delivered together, upon completion of the last job in the batch. Jobs finished before this time have to wait until delivery. There are a delivery cost depending on the number of batches formed and an earliness cost for jobs finished before delivery. The dynamic programming approach to minimizing the total cost is considered, yielding two pseudopolynomial algorithms when the number of batches has a fixed upper bound. A polynomial algorithm for a special case of the problem is also presented.     

New dominance rules and exploration strategies for?the?1|ri|∑Ui scheduling problem

The paper proposes a new exact approach, based on a Branch, Bound, and Remember (BB&R) algorithm that uses the Cyclic Best First Search (CBFS) strategy, for the 1|r _i |∑U _i scheduling problem, a single machine scheduling problem, where the objective is to find a schedule with the minimum number of tardy jobs. The search space is reduced using new and improved dominance properties and tighter upper bounds, based on a new dynamic programming algorithm. Computational results establish the effectiveness of the BB&R algorithm with CBFS for a broad spectrum of problem instances. In particular, this algorithm was able to solve all problems instances, up to 300 jobs, while existing best known algorithms only solve problems instances up to 200 jobs. Furthermore, the BB&R algorithm with CBFS runs one to two orders of magnitude faster than the current best known algorithm on comparable instances.     

Fuzzy scheduling of job orders in a two-stage flowshop with batch-processing machines

In this paper, we present a mixed-integer fuzzy programming model and a genetic algorithm (GA) based solution approach to a scheduling problem of customer orders in a mass customizing furniture industry. Independent job orders are grouped into multiple classes based on similarity in style so that the required number of setups is minimized. The family of jobs can be partitioned into batches, where each batch consists of a set of consecutively processed jobs from the same class. If a batch is assigned to one of available parallel machines, a setup is required at the beginning of the first job in that batch. A schedule defines the way how the batches are created from the independent jobs and specifies the processing order of the batches and that of the jobs within the batches. A machine can only process one job at a time, and cannot perform any processing while undergoing a setup. The proposed formulation minimizes the total weighted flowtime while fulfilling due date requirements. The imprecision associated with estimation of setup and processing times are represented by fuzzy sets.     

Single-machine common due window assignment and scheduling to minimize the total cost

In this paper we consider a single-machine common due window assignment and scheduling problem with batch delivery cost. The starting time and size of the due window are decision variables. Finished jobs are delivered in batches. There is no capacity limit on each delivery batch, and the cost per batch delivery is fixed and independent of the number of jobs in the batch. The objective is to find a job sequence, a delivery date for each job, and a starting time and a size for the due window that jointly minimize the total cost comprising earliness, weighted number of tardy jobs, job holding, due window starting time and size, and batch delivery. We provide some properties of the optimal solution and present polynomial-time algorithms for the problem.     

Batch scheduling and common due-date assignment on a single machine

We consider the problem of scheduling n groups of jobs on a single machine where three types of decisions are combined: scheduling, batching and due-date assignment. Each group includes identical jobs and may be split into batches; jobs within each batch are processed jointly. A sequence independent machine set-up time is needed between each two consecutively scheduled batches of different groups. A due-date common to all jobs has to be assigned. A schedule specifies the size of each batch, i.e. the number of jobs it contains, and a processing order for the batches. The objective is to determine a value for the common due-date and a schedule so as to minimize the sum of the due date assignment penalty and the weighted number of tardy jobs. Several special cases of this problem are shown to be ordinary NP-hard. Some cases are solved in O(n log n) time. Two pseudopolynomial dynamic programming algorithms are presented for the general problem, as well as a fully polynomial approximation scheme.     

Minimizing Weighted Number of Early and Tardy Jobs with a Common Due Window Involving Location Penalty

This paper studies a single machine scheduling problem to minimize the weighted number of early and tardy jobs with a common due window. There are n non-preemptive and simultaneously available jobs. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. The window size is a given parameter but the window location is a decision variable. The objective of the problem is to find a schedule that minimizes the weighted number of early and tardy jobs and the location penalty. We show that the problem is NP-complete in the ordinary sense and develop a dynamic programming based pseudo-polynomial algorithm. We conduct computational experiments, the results of which show that the performance of the dynamic algorithm is very good in terms of memory requirement and CPU time. We also provide polynomial time algorithms for two special cases.     

A new branch and bound algorithm for minimizing the weighted number of tardy jobs

In this paper, the problem of sequencing jobs on a single machine to minimize the weighted number of tardy jobs is considered. Some new dominances between jobs are proposed and studied. A new branch and bound algorithm that can solve large problems, e.g. 85 jobs, is presented.     

机器带不可用时间限制的简单线性恶化供应链排序问题

研究的单机供应链排序问题中, 机器有一个不可用时间限制, 工件的加工时间与恶化率及其开工时间有关, 且工件的加工不可恢复. 一个或多个完工工件可组成一个发送批由车辆发送给客户, 且在机器不可用时间限制之前完工的工件必须在限制开始之时或之前完成发送. 问题的目标是最小化总发送时间与总发送费用之和. 证明问题是NP-难的, 提出了伪多项式时间的动态规划算法. 进一步, 在确定问题目标函数值的上界及下界之后, 设计了一个完全多项式时间近似方案(FPTAS).     

Single machine scheduling to minimize total weighted earliness subject to minimal number of tardy jobs

Motivated by just-in-time manufacturing, we consider a single machine scheduling problem with dual criteria, i.e., the minimization of the total weighted earliness subject to minimum number of tardy jobs. We discuss several dominance properties of optimal solutions. We then develop a heuristic algorithm with time complexity O(n³) and a branch and bound algorithm to solve the problem. The computational experiments show that the heuristic algorithm is effective in terms of solution quality in many instances while the branch and bound algorithm is efficient for medium-size problems.     

Single Machine Scheduling and Selection to Minimize Total Flow Time with Minimum Number Tardy

Emmons considered the problem of sequencing N jobs on a single machine to minimize total flow time with the minimum number of tardy jobs. He proposed an effective branch-and-bound algorithm for this problem. In this paper, we show that Emmons' algorithm can be extended to a more difficult scheduling problem which includes an optimal selection of jobs as well.     

Scheduling with batch setup times and earliness-tardiness penalties

We consider a scheduling model in which several batches of jobs need to be processed by a single machine. During processing, a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. All the jobs in the same batch have a common due date that is either externally given as an input data or internally determined as a decision variable. Two problems are investigated. One problem is to minimize the total earliness and tardiness penalties provided that each due date is externally given. We show that this problem is NP-hard even when there are only two batches of jobs and the two due dates are unrestrictively large. The other problem is to minimize the total earliness and tardiness penalties plus the total due date penalty provided that each due date is a decision variable. We give some optimality properties for this problem with the general case and propose a polynomial dynamic programming algorithm for solving this problem with two batches of jobs. We also consider a special case for both of the problems when the common due dates for different batches are all equal. Under this special case, we give a dynamic programming algorithm for solving the first problem with an unrestrictively large due date and for solving the second problem. This algorithm has a running time polynomial in the number of jobs but exponential in the number of batches.     

Two-stage assembly-type flowshop batch scheduling problem subject to a fixed job sequence

This paper discusses a two-stage assembly-type flowshop scheduling problem with batching considerations subject to a fixed job sequence. The two-stage assembly flowshop consists of m stage-1 parallel dedicated machines and a stage-2 assembly machine which processes the jobs in batches. Four regular performance metrics, namely, the total completion time, maximum lateness, total tardiness, and number of tardy jobs, are considered. The goal is to obtain an optimal batching decision for the predetermined job sequence at stage 2. This study presents a two-phase algorithm, which is developed by coupling a problem-transformation procedure with a dynamic program. The running time of the proposed algorithm is O(mn+n⁵), where n is the number of jobs.     

具有多个不可用时间段的单机供应链排序问题

在单机供应链排序问题中, 机器会有多个长度确定的不可用时间段,它仅可以在可用时间段内加工工件,且每个可用时间段的长度不大于给定的常数.多个完工工件可组成一批由一个容量无限制的运输工具发送给客户.问题的目标是如何 安排工件的加工、发送以及不可用时间段,以使总发送时间与总发送费用之和达到最小. 对于工件加工可恢复的情况,可在多项式时间 O(n^2) 内得到最优序. 对于工件加工不可恢复的情况,证明了问题是强NP-难的, 并提出了~2-近似算法.     

Single Supplier Scheduling for Multiple Deliveries

The problem of scheduling the production and delivery of a supplier to feed the production of F manufacturers is studied. The orders fulfilled by the supplier are delivered to the manufacturers in batches of the same size. The supplier's production line has to be set up whenever it switches from processing an order of one manufacturer to an order of another manufacturer. The objective is to minimize the total setup cost, subject to maintaining continuous production for all manufacturers. The problem is proved to be NP-hard. It is reduced to a single machine scheduling problem with deadlines and jobs belonging to F part types. An O(NlogF) algorithm, where N is the number of delivery batches, is presented to find a feasible schedule. A dynamic programming algorithm with O(N ^F /F ^F–2) running time is presented to find an optimal schedule. If F=2 and setup costs are unit, an O(N) time algorithm is derived.     

Integrated scheduling of production and distribution for manufacturers with parallel batching facilities

We consider a class of integrated scheduling problems for manufacturers. The manufacturer processes job orders and delivers products to the customer. The objective is to minimize the service span, that is, the period lasting from the time when the order is received to the time when all the products have been delivered to the customer. In the production phase, parallel batch-processing facilities are used to process the jobs. Jobs have arbitrary sizes and processing times. Each facility has a fixed capacity and jobs are processed in batches with the restriction that the total size of jobs in a batch does not exceed the facility capacity. When all the jobs in a batch are completed, the batch is completed. In the distribution phase, the manufacturer uses a vehicle with a fixed capacity to deliver products. The transportation time from the manufacturer to the customer is a constant. Completed products can be delivered in one transfer if the total size does not exceed the vehicle capacity. We first consider the problem where jobs have the same size and arbitrary processing times. We propose approximation algorithms for the problem and we show that a worst-case ratio performance guarantee is respectively 2–1/m. Then we consider the problem where jobs have the same processing time and arbitrary sizes. An approximation algorithm is proposed with an absolute worst-case ratio of 13/7 and an asymptotic worst-case ratio of 11/9. Both the proposed algorithms can be executed in polynomial time.