运用半Markov与能力验证的模具企业订单交货期设置

针对模具企业在洽淡阶段难以制定可行的订单交货期问题,建立了一种运用半Markov与能力验证的订单交货期设置模型。利用半Markov状态转移模型演化出订单任务状态的概率分布与需求工期,在演化的同时利用基于有限能力验证的启发式算法验证任务每一状态的需求工期的可行性,得出订单交货期的数学期望。通过实例分析,说明了上述方法对于解决企业实际问题具有一定的实用性。     

No-wait two-machine permutation flow shop scheduling problem with learning effect,common due date and controllable job processing times

We consider a two-machine no-wait permutation flow shop common due date assignment scheduling problem where the processing time of a job is given as a function of its position in the sequence and its amount of resource allocated to this job. The common due date (CON) assignment method means that all the jobs are given a common due date. We need to make a decision on the common due date, resource allocation and the sequence of jobs to minimise total earliness, tardiness, common due date cost and total resource cost. We show that the problem remains polynomially solvable under the proposed model.     

Determination of an optimal common due date and optimal sequence in a single machine job shop

In this paper we consider an n jobs one machine sequencing problem in which all jobs have a common due date and a deviation in its completion time occurs when a job is completed before or after the common due date. The objective is to find an optimal value of this common due date and a corresponding optimal sequence such that the mean absolute deviation of the completion times of the jobs in the optimal sequence from the corresponding optimal common due date is at its global minimum. Starting with an arbitrary sequence we relate the problem to a generalized linear goal program from which some basic results are proved using elementary properties of linear equations and a linear goal programming problem. Using these results and the idea of sensitivity analysis in linear programming, an algorithm is developed that determines the optimal due date and the corresponding optimal sequence yielding the global minimum value of the mean absolute deviation of the completion times of the jobs in the optimal sequence from the corresponding optimal common due date. In the end a numerical example to explain the algorithm is provided.     

Single-item production–delivery scheduling problem with stage-dependent inventory costs and due-date considerations

This paper studies an integrated scheduling problem for a single-item, make-to-order supply chain system consisting of one supplier, one capacitated transporter and one customer. Specifically, we assume the existence in the production stage of an intermediate inventory that works as a buffer to balance the production rate and the transportation speed. Jobs are first processed on a single machine in the production stage, and then delivered to the pre-specified customer by a capacitated vehicle in the delivery stage. Each job has a due date specified by the customer, and must be delivered to the customer before its due date. Moreover, it is assumed that a job that is finished before its departure date or arrives at the customer before its due date will incur a stage-dependent corresponding inventory cost (WIP inventory, finished-good inventory or customer inventory cost). The objective is to find a coordinated production and delivery schedule such that the sum of setup, delivery and inventory costs is minimised. We formulate the problem as a nonlinear model in a general way and provide some properties. We then derive a precise instance from the general model and develop a heuristic algorithm for solving this precise instance. In order to evaluate the performance of the heuristic algorithm, we propose a simple branch-and-bound (B&B) approach for small-size problems, and a lower bound based on the Lagrangian relaxation method for large-size problems. Computational experiments show that the heuristic algorithm performs well on randomly generated problems.     

时间—资源权衡协调问题的多目标优化决策模型

时间—资源权衡协调是以追求资源消耗费用极小和项目完工时间最短为目标，在满足项目工期要求下，根据项目活动时间的先后次序与可更新资源约束有效确定项目时间表。提出了一个具有资源约束问题的时间—资源权衡协调问题的多目标优化决策数学模型。在模型中，对相互冲突的项目工期与整个被消耗的资源费用是可权衡调节的。通过权衡协调和调节项目工期与整个资源消耗费用，得到了满足权衡协调关系的满意可行解，并给出了一个数值算例。此外，在对应于资源约束的Lagrangian松弛表示式中，给出了该二人对策问题的有关特性。     

Due date assignment in single machine with stochastic processing times

This paper considers two different due date assignment and sequencing problems in single machine where the processing times of jobs are random variables. The first problem is to minimise the maximum due date so that all jobs are stochastically on time. It is shown that sequencing the jobs in decreasing service level (DSL) order optimally solves the problem. The results are then extended for two special cases of flow shop problem. The other problem is to minimise a total cost function which is a linear combination of three penalties: penalty on job earliness, penalty on job tardiness, and penalty associated with long due date assignment. The assignment of a common due date and distinct due dates are investigated for this problem. It is shown that the optimal sequence for the case of common due date is V-shaped.     

A double-layered optimisation approach for the integrated due date assignment and scheduling problem

As the market competition becomes fiercer, contemporary make-to-order firms are confronted with both due date quotation and production scheduling problems at the same time. On the one hand, in order to attract customers, the firm needs to quote a short lead time; on the other hand, once a due date has been promised, the firm must spare no effort to deliver the goods no later than this date. If due date assignment and shop scheduling are processed separately by two systems, the overall performance is unlikely to be satisfactory because the two tasks are actually interrelated (e.g. a tighter due date setting will increase the chances of tardiness despite its appeal for the incoming customer). Therefore, we consider the problem by integrating due date assignment and shop scheduling into one optimisation model. A double-layered heuristic optimisation algorithm is presented for solving this problem. In the upper-layer genetic algorithm which performs coarse-granularity optimisation, Bayesian networks are used to learn the distribution of optimal due date values. As the second-layer algorithm, a parameter perturbation method is applied for a finer-granularity neighbourhood search. Computational experiments prove the efficacy and efficiency of the proposed algorithm.     

A particle swarm optimisation for the no-wait flow shop problem with due date constraints

This paper considers the no-wait flow shop scheduling problem with due date constraints. In the no-wait flow shop problem, waiting time is not allowed between successive operations of jobs. Moreover, a due date is associated with the completion of each job. The considered objective function is makespan. This problem is proved to be strongly NP-Hard. In this paper, a particle swarm optimisation (PSO) is developed to deal with the problem. Moreover, the effect of some dispatching rules for generating initial solutions are studied. A Taguchi-based design of experience approach has been followed to determine the effect of the different values of the parameters on the performance of the algorithm. To evaluate the performance of the proposed PSO, a large number of benchmark problems are selected from the literature and solved with different due date and penalty settings. Computational results confirm that the proposed PSO is efficient and competitive; the developed framework is able to improve many of the best-known solutions of the test problems available in the literature.     

Optimal due date quoting for a risk-averse decision-maker under CVaR

This study investigates a due date quoting problem for a project with stochastic duration, taking the decision-maker’s risk attitude into consideration. The project profit is defined as the difference between the price and the cost that is comprised of production cost and earliness–tardiness penalties. In this situation, the due date determination has to be modelled as a stochastic optimisation due to stochastic duration. Conditional value at risk is thus employed as a performance measure to describe the decision-maker’s risk attitude. In fixed price contract, when the unit production cost is not smaller than the unit penalty on earliness, the optimal due date increases with the increase of the degree of a decision-maker’s risk aversion, the unit penalty on delay, and the decrease of the unit penalty on earliness. Besides, when the price is proportional to the due date and the slope is no bigger than the unit penalty on tardiness, the optimal due date is smaller than the result in fixed price. This is because high price for a short due date encourages a decision-maker to quote a small due date. Further, we compare the optimal due date in different parameter setting where the penalty coefficient of earliness is negative or zero, which means there is reward or no penalty on earliness, respectively. Finally, a case study is conducted to validate the effectiveness and efficiency of the proposed model.     

MTO运营模式的订单交货期决策模型

承诺交货期过晚,没有时间优势,容易丢失订单;承诺交货期过早,企业超负荷生产,增加生产成本,可能出现亏损。针对基于订单式生产(MTO)的中小制造企业的客户订单交货期预报问题,综合考虑价格、订单需求量、提前完工和延期交货损失、加班、外协和损耗率因素等对任务完工期的影响,以收益最大化为目标,建立了订单任务交货期决策模型,并运用Matlab编程和计算工具对实例进行分析,验证了模型的有效性。模型对MTO生产企业交货期决策具有一定的参考意义。     

Scheduling jobs with proportionate early/tardy penalties

We address the problem of scheduling jobs subject to proportionate early/tardy penalties. The problem is known to be NP-complete. We identify interesting special cases, and develop polynomial time procedures for solving them optimally. It is shown that the shortest processing time rule is optimal when due dates are set using the widely known total work content rule or the equal slack rule. If jobs have a common due date, many alternative optimal solutions exist, and the longest processing time rule yields an optimal sequence. Also, a simple formula is provided for determining the optimal start times forjobs in the common due date problem. Our results for the common due date problem generalize and extend earlier research. Further extensions are discussed.     

Scheduling of storage/retrieval orders under a just-in-time environment

We consider the problem of scheduling storage and retrieval orders under dual-command operations in a unit-load automated storage/retrieval system. The objective is to minimize the weighted sum of earliness and tardiness penalties about a common due date. We propose four heuristics based upon a two-step approach where dual-command cycles are formed first and then optimally scheduled. A mixed-integer programming model is also formulated to obtain an optimal solution. Performances of the heuristics are compared in the simulation tests. Computational results show that some heuristics perform favourably.     

Effectivity date analysis and scheduling

The impact of design on logistics cannot be ignored, and design for logistics is a new concept similar to design for manufacturing or design for assembly. Engineering change is one of the scenarios that would require logistics support. Change control of a product data management (PDM) system is one of the major approaches for handling engineering changes today. According to principles of configuration management, during the change control workflow, there are three different dates: release date, effective date, and effectivity date utilised for controlling and managing change planning and scheduling. Effective date is the exact date that a released change takes effect to the shop floor workshop. Effectivity date is the expected date that decision makers plan for the change to take effect. In normal situations, multiple disciplines, such as design and development, purchasing, shop floor workshop, quality control, and so on, are involved in making a change decision on when a change is to become effective. In this paper, a linear programming effectivity decision model is proposed to concurrently support changes of design scheduling, and production planning and scheduling when an engineering change occurs. The proposed model succeeded in solving an integration problem of design scheduling, production planning and shop floor scheduling.     

Algorithms for the joint multitasking scheduling and common due date assignment problem

In this paper, we investigate a joint multitasking scheduling and common due date assignment problem on a single machine, for which examples can be found in product delivery process in logistics. Multitasking allows the machine to perform multiple tasks. The multitasking phenomenon has been observed in various practical domains, including manufacturing and administration. In multitasking settings, each waiting job interrupts a currently in-processing job, causing an interruption time and a switching time. In common due date assignment problems, the objective is to determine the optimal value of this due date with the purpose of minimising a total penalty function, which is associated with service quality. For the problem with general interruption functions, analytical properties are obtained to reduce the search space of the optimal solutions. For the cases with linear interruption functions, we develop a polynomial-time algorithm. Numerical experiments have been conducted to validate the efficiency of our proposed algorithm. Computational results also demonstrate an interesting phenomenon that in some cases, the optimal solutions under multitasking are superior to the counterparts without multitasking. Besides, we also devise a mixed integer programme for the cases with linear interruption function.     

Machine scheduling in the presence of sequence-dependent setup times and a rate-modifying activity

Rate modifying activity (RM) is a type of maintenance after which the processing rate of the machine increases. RM is a very new topic in academic studies. However, it is very common in real world situations. In this paper, we study the integrated problem of assigning a common due-date to all jobs, scheduling the jobs and making decisions about the position of RM in a single machine environment in which the setup times are sequence dependent. The objective is minimising the summation of earliness costs, tardiness costs and due date related costs. This problem has never been studied in the literature with any arbitrary criterion. We construct a time-dependent travelling salesman problem (TDTSP) formulation for this problem. The position of the optimal common due date and some dominance properties for the position of RM are presented. A branch and bound (B&B) procedure is developed to solve the problem optimally. Numerical results justify the effectiveness of the B&B method for small problems. For larger problems, two robust metaheuristics are proposed.     

Single-machine scheduling and common due date assignment with potential machine disruption

This paper studies a single-machine due date assignment and scheduling problem in a disruptive environment, where a machine disruption may occur at a particular time that will last for a period of time with a certain probability, and the job due dates are determined by the decision-maker using the popular common due date assignment method. The goal is to determine jointly the optimal job sequence and the common due date so as to minimise the expected value of an integrated cost function that includes the earliness, tardiness and due date assignment costs. We analyse the computational complexity status of various cases of the problem, and develop pseudo-polynomial-time solution algorithms, randomised adaptive search algorithms, and fully polynomial-time approximation schemes for them, if viable. Finally, we conduct extensive numerical testing to assess the performance of the proposed algorithms.     

ON THE DUALITY APPROACH TO OPTIMAL DUE DATE DETERMINATION AND SEQUENCING IN A JOB SHOP

This paper considers the problem of finding an optimal CON due date and sequencing of n independent jobs to be processed on a single machine by minimizing the total value of lateness. A linear programming model is developed to find an optimal CON due date which is solved by considering its dual. A procedure to find the optimal job sequence is then presented and elaborated by a numerical example.     

Permutation flow shop scheduling with earliness and tardiness penalties

We consider the permutation flow shop scheduling problem with earliness and tardiness penalties (E/T) and common due date for jobs. We show that the problem can be sub-divided into three cases: (i) the due date is such that all jobs are necessarily tardy; (ii) the due date is unrestricted; and (iii) the due date is between the two. Based on analytical results we provide partial characterisation of the optimal solution and develop a comprehensive approach for solving the problem over the entire range of due dates. Our approach, which draws upon the existing literature and results for the single machine problem, successfully exploits the properties of the optimal solution. Limited computational results indicate that the performance of the heuristic is reasonable and has the potential to significantly improve performance. This approach has been incorporated as part of the scheduling module of the production planning and scheduling system we developed for a medium-sized bulk drug manufacturer.     

Integrated model for the batch sequencing problem in a multi-stage supply chain: an artificial immune system based approach

In this paper a mathematical model for the batch sequencing problem in a multistage supply chain is developed by taking into account three practically important objectives, viz. minimization of lead time, blocking time and due date violation. Attribute dependent operation time, sequence dependent setup time, different due dates, different lot sizes for batches and variable time losses due to interaction among several stages like waiting, idling, and blocking are also considered in the model. The problem is combinatorial in nature and complete enumeration of all its possibilities is computationally prohibitive. Therefore, a metaheuristic, artificial immune system (AIS) is employed to find an optimal/near optimal solution. In order to test the efficacy of AIS in solving the problem, its implementation on four different problems has been studied. Further, the comparative analysis of the results obtained by implementing AIS, genetic algorithm (GA) and simulated annealing (SA) on the proposed model reveals that AIS outperforms GA and SA in solving the underlying problem.     

Common due date assignment scheduling for a no-wait flowshop with convex resource allocation and learning effect

This article addresses the no-wait flowshop scheduling problem with simultaneous consideration of common due date assignment, convex resource allocation and learning effect in a two machine setting. The processing time of each job can be controlled by its position in a sequence and also by allocating extra resource, which is a convex function of the amount of a common continuously divisible resource allocated to the job. The objective is to determine the optimal common due date, the resource allocation and the schedule of jobs such that the total earliness, tardiness and common due date cost (the total resource consumption cost) are minimized under the constraint condition that the total resource consumption cost (the total earliness, tardiness and common due date cost) is limited. Polynomial time algorithms are developed for two versions of the problem.