Search

The occurrence of disasters often causes a large number of wounded persons. The rapid rescue and transport of wounded persons for medical care is a key concern of emergency management. To maximize the number of survivors, we propose a new transport strategy based on injury classification, called the Red-Yellow-Green-Sequential (RYGS) transport strategy, which prioritizes the transport order by the degree of injury of the wounded persons. To solve this intractable problem, we propose an improved ant colony optimization algorithm (IACO) to solve it approximately. IACO not only involves a pheromone updating method according to the characteristics of the problem itself, but also combines the particle swarm optimization algorithm and the genetic algorithm to avoid local convergence. Through numerical studies, we demonstrate that IACO outperforms ACO under different transport strategies in different scales and scenarios. In addition, we demonstrate through numerical studies the superiority of RYGS among three transport strategies in different scenarios and scales. We also demonstrate that the combination of IACO and RYGS performs best in different scenarios and scales. Finally, we conduct a sensitivity analysis to analyze the impacts of the different medical resources on the objective for the problems with different combinations of scales and scenarios based on IACO. We also discuss the practical implications of the findings for emergency management.

We consider the problem of scheduling n nonresumable and simultaneously available jobs on a single machine with several agents. Each job belongs to one of the agents, each of which competes for the use of the machine to process its own jobs to meet its own scheduling criterion. The machine has a fixed interval during which it is unavailable to process the jobs. The due dates of the last agent’s jobs are decision variables, which are determined by the unrestricted (different) due date assignment model, while the due dates of each of the other agents’ jobs are given in advance. The last agent wishes to minimize the sum of the due date assignment cost and weighted number of its tardy jobs, while each of the other agents seeks to minimize the maximum value of a regular scheduling function of its jobs, the total completion time of its jobs, or the weighted number of its tardy jobs. The overall objective is to minimize the last agent’s criterion, while keeping each of the other agents’ criterion values no greater than a given limit. We analyze the computational complexity, and devise pseudo-polynomial dynamic programming (DP) solution algorithms and mixed integer linear programming (MILP) formulations for the considered problems. Finally, we compare the performance of the DP solution algorithms against the corresponding MILP formulations with randomly generated instances.

Integrated production and batch delivery scheduling with two agents is considered.Constrained optimization problems on various criteria of the two agents are addressed.Computational complexity status and solution procedures are developed for the problems.Numerical studies are conducted to evaluate the performance of the algorithms. We consider integrated production and batch delivery scheduling in a make-to-order production system involving two competing agents, each of which having its own job set competes to process its jobs on a shared single machine. To save the delivery cost, the jobs of the same agent can be processed and delivered together batches. The completion time of each job in the same batch coincides with the batch completion time. A batch setup time is incurred before the processing of the first job in each batch. Each of the agents wants to minimize an objective function depending on the completion times of its own jobs. The goal is to determine a schedule for all the jobs of the two agents that minimizes the objective function of one agent, while keeping the objective function value of the other agent below or at a given value. For each of the problems under consideration, we either provide a polynomial-time algorithm to solve it or show that it is NP -hard. In addition, for each of the NP -hard problems, we present a mixed integer linear programming (MILP) formulation and provide a pseudo-polynomial dynamic programming algorithm, establishing that it is NP -hard in the ordinary sense only, and show that it admits an efficient fully polynomial-time approximation scheme, if viable. Finally, we compare the performance of the pseudo-polynomial dynamic programming algorithms against the corresponding MILP formulations with randomly generated instances.

We study some two-agent single-machine scheduling problems with increasing linear job deterioration.We consider six different combinations of two-agent objective functions.We discuss complexities and develop polynomial-time algorithms of the proposed problems. We consider several two-agent single-machine scheduling problems with deteriorating jobs. By deteriorating jobs we mean that the actual processing time of any job of the two agents is an increasing linear function of its starting time. Each agent wants to minimize a certain objective function, which depends on the completion times of its jobs only. The goal is to schedule the jobs such that the performance of the schedule is satisfactory with respect to the objective functions of both agents. We consider six scheduling problems associated with different combinations of the two agents' objective functions, which include the maximum cost, total weighted completion time, discounted total weighted completion time, maximum earliness cost, total earliness, and total weighted earliness. We examine different scenarios depending on the trade-off between the two agents. Under each scenario, we address the computational complexity and solvability issues of various problems that seek to find the optimal solution for one agent, subject to an upper bound on the maximum (earliness) cost of the other agent.

We address two scheduling problems arising when two agents (agents A and B ), each with a set of jobs, compete to perform their respective jobs on a common machine, where the due dates of agent A ’s jobs are decision variables to be determined by the scheduler. Specifically, the objective is to determine the optimal due dates for agent A ’s jobs and the job sequence for both agents’ jobs simultaneously to minimize the total cost associated with the due date assignment and weighted number of tardy jobs of agent A , while keeping the maximum of regular functions (associated with each B -job) or the number of tardy jobs of agent B below or at a fixed threshold. We prove that both problems are NP -hard in the strong sense and develop polynomial or pseudo-polynomial solutions for some important special cases.

We consider single-machine batch delivery scheduling with an assignable common due date and controllable processing times, which vary as a convex function of the amounts of a continuously divisible common resource allocated to individual jobs. Finished jobs are delivered in batches and there is no capacity limit on each delivery batch. We first provide an O(n^5) dynamic programming algorithm to find the optimal job sequence, the partition of the job sequence into batches, the assigned common due date, and the resource allocation that minimize a cost function based on earliness, tardiness, job holding, due date assignment, batch delivery, and resource consumption. We show that a special case of the problem can be solved by a lower-order polynomial algorithm. We then study the problem of finding the optimal solution to minimize the total cost of earliness, tardiness, job holding, and due date assignment, subject to limited resource availability, and develop an O(nlogn) algorithm to solve it.

e consider a single-machine batch delivery scheduling and common due date assignment problem. In addition to making decisions on sequencing the jobs, determining the common due date, and scheduling job delivery, we consider the option of performing a rate-modifying activity on the machine. The processing time of a job scheduled after the rate-modifying activity decreases depending on a job-dependent factor. 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 common due date for all the jobs, a location of the rate-modifying activity, and a delivery date for each job to minimize the sum of earliness, tardiness, holding, due date, and delivery cost. We provide some properties of the optimal schedule for the problem and present polynomial algorithms for some special cases.

Scheduling with learning effects has received growing attention nowadays. A well-known learning model is called ''sum-of processing-times-based learning'' in which the actual processing time of a job is a non-increasing function of the jobs already processed. However, the actual processing time of a given job drops to zero precipitously when the normal job processing times are large. Motivated by this observation, we propose a truncation learning model where the actual job processing time is a function which depends not only on the processing times of the jobs already processed but also on a control parameter. The use of the truncated function is to model the phenomenon that the learning of a human activity is limited. Under the proposed learning model, we show that some single-machine scheduling problems can be solved in polynomial time. In addition, we further provide the worst-case error bounds for the problems to minimize the maximum lateness and total weighted completion time.