Discrete time parallel-machine scheduling: A case of ship scheduling

Parallel-machine scheduling concerns scheduling a number of jobs on more than one processor working in parallel. A medium-term ship scheduling problem frequently encountered in ports is the scheduling of arriving ships so as to minimize the total demurrage cost incurred. This problem is in fact a parallel-machine scheduling problem, and can be formulated as a pure zero-one integer program when time is discrete. Different from the usual parallel-machine scheduling studies, the ready time of each job is not required to be identical. As an illustration, the ship scheduling problem faced by China Steel Corporation in Taiwan is discussed and solved. The proposed model is applicable to other deterministic parallel-machine scheduling problems in whic jobs have to be processed continuously on the same or different machines.